Mine plays most songs, some come up with incorrect titles, etc. Now I think the best solution is to delete/resync library it seems when i deleted my icloud songs which couldnt play, i redownloaded them and they work perfectly.
I was having some problems before but, since I jailbroke my 4s I was getting a lot more problems with the music app. I'm using iTunes match and deleted all my music on the phone from within settings and have redownloaded a few playlists and everything seems to be working good now.
Honestly, the music/ipod app has been glitchy for me IN GENERAL since iOS 5. And don't get me started on iCloud! For the most part it's good, but the reliability that was in the iOS 4 music app never caused problems.
That said, I'm running mine jailbroken. I turned off match in music settings, deleted all music from my phone, closed all apps, did a hard reset, and when it came back on turned on match again and everything worked fine.