I recently upgraded my old iPhone 3G to iOS 4.1; I'd heard the horror stories about the abysmal performance that iOS 4.0 had with the older phone, so I waited until Apple had the fix. Everything went well with the upgrade; I think my phone might actually be a little faster. But then I tried playing some music.
A large portion of my library just wouldn't play. I'd select a song and the iPod app would try to play it for a second or two, and then it would move on to the next song. Sometimes there would be a string of songs that it would go through like this before actually playing one. It was maddening, because a large portion of my library seemed unplayable.
After a bit of testing, it appeared that only my MP3 files were not playing. Strangely enough, my MP3 podcasts would play fine; only the music files were affected. Songs encoded with AAC played fine. The weird thing is that only the songs that are MP3 on my computer would not play, since on my iPhone they are all AACs (I have everything converted to 128kbps AAC as it loads onto the phone to squeeze every last byte out of the hard drive). I know, none of this really makes any sense.
Anyway, the fix appears to be removing all the music from the iPhone and then re-loading it. It takes a while, but I can finally listen to my music again. If you're having the same problem, give this a try.