I found FlipSide and like it... they had a Blog article about it a few months ago... it does cost some money, but they had it available on CB.com... you might also look around on App World.
I replaced my Pandora with Slacker Radio through the Blackberry App Store. Still free, still occassional adds, but WAYYY more stable than Pandora. Enjoy!