A lot of folks are very disappointed with the new Music App (that replaced the original iPod App) with iOS 5 on the iPad. There are a few alternative music players available that should work, at least until Apple gets the bugs out of and updates the Music App.
I tried several, both free and paid and the one I'm using now is called "Groove" for the iPad. It's not the best UI and it has some odd bells and whistles, but it does recognize my Smart Playlists and the performance is fairly smooth and fast. It has the ability to create Pandora-like playlists based on your choices as well. I haven't explored many of its features, I just wanted a music player that would work. That's my recommendation for now. I'm sure others will chime in with some additional suggestions.
Best of luck and let us know what you end up using!