I use Pandora, Last.fm, and Droid Live. I haven't had significant problems with all three except the buffering issue on Droid Live if you drive around with it. Hopefully, you will find happiness with something else.
i love the app on my droid helluva lot better than it was on my storm. only thing that i have had happen was ONCE it switched stations on me...idk how or when but i was digging it then realized it was a different genre