It's happening to A LOT of people. It's all over various forums. I had the problem. the general solution seems to be to delete all music from your iPhone, then sync it back. I had to do it 5 times, and I still had a few issues, all of which I managed to resolve. There were some duplicate songs (solution: delete the first one of the duplicates). I had to download a few from the iTunes store (just tap the download icon next to the song). One of the songs I had cross-loaded took a zillion tries to get back on the phone, but it eventually worked. Don't ask me how I did it.
Major, though not critical, bug on Apple's part. All that beta testing... The problem is when you have users doing the testing is that there is no test plan that covers all the features. They just sort of hope that with the number of users testing, everything gets tested. Bit it ain't so...