I know it's been said on here... but to hopefully add to the "solution" pile...
Following recommendations on here, I simply unchecked iTunes Match in iPhone... then unchecked "Sync Music" in iTunes, sync'd, (it deletes all music from phone)... rechecked "Sync Music" sync'd again... waited till all music went back, all good.
I'm not sure what part of all that was absolutely necessary... likely the "unsync/resync music part... at any rate, it's working now.
Good luck all.
OK so I have been annoyed with this but not been bothered to do anything about it until today...my itunes match was unticked but whether I tried to download straight to the phone or sync through itunes it just wouldn't work. I erased all content and settings then restored to itunes back up and for some reason now it works. Some of the things people were suggesting sounded so long and complicated I had decided it really couldn't be that difficult so didn't bother. Thankfully it worked with the restore because I was thinking that might put all the settings to exactly how it was.
Thanks for everyone's posts .. after much similar frustration the "Un-Sync Music" strategy worked for me, but I did want to share something else that may help some folks locate "missing songs":
Background: I am running iTunes (184.108.40.206) on a PC, connected to iPhone 5 (7.0.4).
My symptoms were:
I purchased songs through iTunes. All of them appeared in my Purchased folder, and also in my iPhone5 device folder that appears when it is plugged into my PC. But some of them were greyed out in list (and had a 'dotted circle'next to them) .. and on the iPhone side, the songs appeared in my list, but I was persistently asked to download them from the cloud. I could do this manually (per song), but after each re-sync my phone would go back to showing each of these particular songs needed to be downloaded.
I followed the recommendation by unchecking the 'Sync Music' check box, then clicking 'Apply'. For good measure, I unplugged my phone from the PC then powered it off; then closed down iTunes.
I then powered up my iPhone, plugged it into my PC .. iTunes started automatically and went through its reguar sync process.
I assumed that (because while during the process of unchecking 'Sync Music' there was a warning that said doing so would delete all my songs from my iPhone) .. my songs would be deleted .. but they weren't. Since that wasn't my objective I didn't pursue it, but did think it odd.
For good measure, I unplugged my iPhone, powered it down, and exited iTunes .. then powered up my iPhone, connected it to my PC .. iTunes started up a went through it's sync process.
After which I checked 'Sync Music' then selected 'Apply' .. and voila, iTunes went through the process of syncing my entire music library, including the problematic songs (I have about 950 songs, of which 475 were purchased through iTunes).
Upon inspection of my iPhone5 Device folder in iTunes .. the 'greyed out with dotted circle' songs remained in place, but duplicate "functioning' copies were added. Since only one copy appeared on my phone 'no harm no foul' .. but I wonder what/why the 'corrupt' versions were being kept in the folder .. a case of 'whatever'.
The "something else" I referred to at the top relates to the fact that it appeared that despite my success, a small number of songs still didn't appear on my phone .. or so I thought.
In fact they had been transferred, since when I looked for them by song title instead of artist they showed up.
The (frustrating) problem was this: where a song is part of a compilation album of 'various artists' iTunes selects the Artist field .. whereas iPhone5 selects the Album Artist field.
To understand this, click on a song in iTunes, right click (apologies to Mac'ophiles) on the song, select Get Info, then select the Info tab.
To correct this problem of incompatibility between iTunes and iPhone (can we all seriously believe this?!?! Maybe the respective engineering teams are on different continents .. or more likely different planets ..but I digress) .... simply edit the Album Artist to read the same as Artist ..
.. and as if by magic .. the missing tracks will appear under the correct artist in your iPhone!
Hope this was useful .. apologies for the 'long hand' but figured maybe some folks would appreciate the blow by blow detail ..
And with that (Apple, please take note) .. after four hours of frustration, I will get back to my day job!!