This happened to me, what I did to fix it was go into ipod setting, take off the eq and shake to shuffle. Hard reset (hold home and power until apple logo comes back up), then plug into itunes, let it sync, and then it worked for me.
My phone said i had like 6gb of audio, but no songs, lol... all fixed now.