I hear great things about Spotify from lots of people...but I'm pretty sure my experience would mirror this guy's:
"Jam Session: Grading Spotify on Jazz Terms" | San Diego Reader
It's jazz and classical music that fucks it up mostly, because each individual performance of piece by a different performer has it's own distinct quality.
So, while sometimes, I think "I want to hear some Charlie Parker today", and I think Spotify would be great for that, sometimes I think "I want to hear the Charlie Parker solo from "Moose the Mooch" that he recorded in Toronto in 1953 as opposed to the 20 or 30 other recordings I have of him playing that tune" and I think I'd wind up frustrated by Spotify in those situations.