Well now im sorry but im out of suggestions

Is your phone up to date ??
It certainly is a bizarre situation you have.
One last thing, navigate to Macintosh HD >> Library >> Preferences >> com.apple.itunes.secure.plist and drag that to the desktop, after shutting down iTunes before hand. then see what happens.
If nothing then, lets hope someone else will pop in with another suggestion.
EDIT : What i cant understand is why it it trying to sync songs when you have the songs in the cloud then they are available on any device, so it should only be the song names on you iPhone not the song itself as they are in the cloud ?!?!?!? ::scratches head::
EDIT 2 : Please dont cross post as it starts to get confusing. The Mods will either delete or merge that other thread you started.