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.