Pandora is the best of a bad lot. They have an interesting approach, but any lengthy listen will reveal a lot of repetition; not because there's a tiny universe of music to recommend, but rather because they can't afford to troll the long tail (downloading stuff from Bandcamp, for instance). What works for Pandora is their curation, and the marginal cost of increasing inputs is more than they are willing to spend.
The last record I bought (a single by The Greys) I listened to on recommendation of a coworker, who's in a band that I like, who had played with some people who are playing a show with The Greys. I also like going to a local record store (Soundscapes) and just buying what the people who work there recommend. Nobody is currently capturing these signals; Facebook is obviously the one company that has access to perhaps a sufficiency of this data, but music recommendations are seemingly pretty small beer in the Zuckerbergian scheme of things.
The lack of a decent music (or film/TV) recommendation system looks a lot like a business opportunity, but I think that it's fundamentally not a business. Recommendations can drive business to a retail operation, but how do you sell recommendations qua recommendations?
I am not sure if I would say algorithmic music discovery have failed but yes, I would pick curation over algorithms any day. It just gives me more context.
