I took a chance and wrote down all my songs or the majority of them (you don't have to) figuring that I was going to delete them and reinstall them.
On my phone (Droid Incredible) went to my Settings, Applications, Rhapsody, Clear Data, and Unistall from my phone. I then went to the new Play Store (market) and searched for Rhapsody and reinstalled the app. It seems to be working so far. All my songs seem to be playing. There must be something wrong with the updates. I have noticed that I can't connect my phone to the computer and download my songs that way anymore, only from my phone.
Try it. See what happens. What do you have to loose, songs that you can't listen too...