I spent over a month fighting with the same problem. I found a program called "mp3val" version 0.1.7 and scanned the iTunes music folder. It found approx 50 errors and I selected them and hit fix. now my 6600 songs sync correctly. This was with iTunes version 8.

I had tried uninstalling and reinstalling iTunes, downgrading to an older iTunes, and restored my iPod to factory settings several times. None of that worked.

It seems that iTunes corrupted the songs during a patch. The songs were fine before two minor patches ago.