After updating my iPhone 3GS to iOS 5.0.1 from 4.3 on Sunday Evening, and letting it finish syncing, I tried playing my music in the morning. I thought it was great that it held the last song I was playing, but it never actually played it. I hit Play, the play logo appears on the status bar. The Pause button switches back to Play on the iPod Controls screen. I can hit Next or Previous, and it does the same thing. One about 1 out of every 20 songs, it will play a song, although all the tags are matched up to a different song.
I tried Resyncing, with a cable and over Wifi for the past couple of nights, but the same thing keeps happening. I am running iTunes 10.5.1 on a MacBook Pro with OSX 10.6.8