Now that that's gone, they're just another dime-a-dozen paid music streaming services that nobody wants to pay for.
edit: For anyone wondering what the big deal with Spotify is, is that it was completely free. Anyone could just download the app, and then listen to any song they wanted to, legally, completely free - there were just short ad breaks every couple of songs. This free legal option meant that there was zero reason to pirate music anymore, so everyone flocked to it.
If you paid €10/mo you got a higher bitrate, no ads, offline playing and access to the iPhone/Android apps. The pay option was attractive if you were going to have a party (ads are a turnoff in situations like that), or when you end up requiring the iPhone app since you don't have any music files to put on your MP3 player anymore since you've just been listening to everything on Spotify...
The record companies really hated giving away music (despite Spotify being a goldmine for them - Spotify is currently the #1 single source of income for record labels in Sweden, making them more money than any single retailer), so they had to kill it a couple months back (rumor has it they had to kill it in order to secure U.S. rights).
Without the completely free tier, they'll have a really hard time getting new users.