With Rhapsody already available on the iPhone and Android it is no shocker that they are now publicly beta testing a BlackBerry client. I am still waiting for the upcoming premium version of Slacker but Rhapsody did a nice job with this music subscription app. The only real catch is that it looks like the service is US only for now.
Blaze mentioned the app on CrackBerry and it looks like it has been around for a bit in private beta and recently became publicly available. The app comes with a free 7 day trial of unlimited music from Rhapsody to check it out. You can get over 10 million songs through the app so the catalog should keep you busy.