Bitcoin is something that has really started to come out into the open a little more just recently. So far, there are many companies that are accepting bitcoin for online purchases or subscriptions. Reddit is officially taking bitcoin as payment for reddit gold, and Mega, owned by Kim Dotcom, has recently started to accept bitcoin for it's data storage service. I understand that bitcoin is still a fairly small thing at this point, but the implementation of that into a service like spotify seems to be a perfect match. From everything that I have heard, bitcoin implementation is not that complicated, and I think this would make it very easy for many people to pay for the premium accounts!
reddit.com/r/bitcoin is a good place to start for the questions of "what is bitcoin?" They have a lot of links on the side bar that are very informative.