I dont know if this is new or not, but its in the verizon section. I like rhapsody, used it with my voyager..
Not new and not beta anymore (I think), I've had it running for a few months now (there was a thread on it a while ago). It's a great service. Rdio is setting up in competition but for now Rhapsody works great for me.