I have the same issue after upgrading my iPhone 4 to iOS 6.
I finally set up my iPhone 5 last night. Tried to play a few songs on it only to watch as the music app skipped through sometimes hundreds of songs. These songs played perfectly fine on Tuesday from my 4s before I switched over to the iPhone 5. Has anyone else had this problem?