OK, so I just took a good look at this problem today. I usually listen to Pandora most of the time, so while I I seem to have noticed this in the past, I just assume it was a glitch that would be corrected.
Today I first did the resyncing suggestion twice. What that did was remove those tracks that were shown on my iPhone (5) but when selected would just skip it. There were around 600 songs that did seem to make it back to my iPhone after the resync method tried above. In iTunes (on the computer) I located the actual files in the iTunes folder (computer>users>username>music>iTunes>itnunes music) and found that the files not playing were m4p or m3a, which appear to be protected files from the DRM days. For those that don't know what that is, it'll be the music you purchased a couple years back. At one point, Apple allowed you to upgrade your DRM music for the difference of the unprotected version (iTunes plus), however that option is no longer available.
I don't know if this issue came up when I upgraded from my 3GS to the 5, or if it came in with one of the iOS updates, but I do know that I could listen to all my music on my 3GS when I regularly listened to my music library (before I found Pandora).
As a last ditch effort, I decided to go ahead and take a look at the tutorial video under the help menu while in iTunes. Watching "iTunes in the Cloud", I found the solution. In iTunes on your Mac, open preferences and then click "Store", look for and select "Show iTunes in the Cloud purchases", then click OK. In iTunes, you'll see Cloud icons in various ways depending on your selected viewing option. For now, select the "Albums" view. You'll see the "Cloud" icon in the upper right hand corner of the album, clicking that will download the entire album. I haven't tried syncing my phone back to mu computer to see of the song transfers, but I'd imagine it does, however it appears or create duplicates of the song within your iTunes music library, I assume you can move the DRM files to another folder within iTunes to eliminate the duplicates, but that's a different issue so I'll end that there.
The other way to get that music on your iPhone and is the method I used, is to download it directly to you iPhone. Open the iTunes app on your iPhone, this is not the orange "Music" app located in the dock by default, it is a purple/violet colored app that says "iTunes". Open that app and on the bottom select more, from there select "Purchased", then "Music", then "Not on This iPhone". From there you just select the albums and click on the Cloud icon with the down arrow to download the music.
I should mention that if you've previously purchased the music, there does not appear to be any up charge for downloading this music as was the case with iTunes Plus. Also, you don't need to turn on iTunes Match, I have not and still don't.
Why Apple customer service hasn't been able to identify this problem per those that contacted CS is beyond me, but it seems the biggest issue is confusion caused by a lack of clear instruction to users. Personally, I think this should be automatic.