Odd are, that the missing songs are protected by DRM (Digital Rights Management). It prevents any device not by apple from playing it. Were the missing songs bought on iTunes?
You need to remove the DRM. To do this, either upgrade the songs to iTunes Plus, or if it is not available for them, burn them to a CD, then copy the songs from the CD to your computer. This will remove the DRM from the songs. Put the songs from the CD on your phone, and they should show up. Good luck!