I went to spotify.com and requested an invite and got it roughly 30 seconds later. Either I'm really cool or it's not that hard.
I used Youtube to listen to full songs before, and just glancing at Spotify it doesn't seem like that will change much. Cool idea, but they seem to be missing a lot of music.
