I am one of the few people who are lucky enough to be a beta tester for Spotify. The timing could not have been better, since Pandora has recently been blocked outside of the U.S.
Other people have analyzed Spotify in their blogs, so I won't do that here. Suffice to say that I love it and use it all day at work and all evening, every day and I have not had any problems and I have found almost all the music I want to listen to.
My two cents to add is that Spotify has an amazing team of developers. My friend Jon of course, who is probably mostly famous as one of the inventors of the Shakespeare Programming language. But also, they have managed to hire a couple of PhDs from KTH who are arguably the best programmers in the world.
I think the strong team combined with a really good product will make Spotify a winner, and if I had a couple of (million) dollars to invest, I sure know where I'd put them.