My real problem is finding what I want to listen to at this very moment, and managing it. I don't want to spend forever finding my music, downloading it, arranging payment, organizing it, backing it up, copying it to my iPod or other computer, etc.
Spotify gets this: search -> listen -> add to playlists. At work, home, wherever... just login. Girlfriend's music? Switch user. Throw away my iPod, it was just a shipping container, anyway.
It solves the organisation problem very neatly. Piracy will find it hard to compete.
Piracy still is the market leader in catalogue size and ease of use for consumers at large (just see the AVC post in another comment). This is actually a fantastic way to look at it - Spotify didn't set out to beat iTunes or any existing market player with a business model, they wanted to beat piracy.
Now that's an ambitious goal, even though many other services aim at doing the same indirectly (by beating existing market players).
Serious pirates are all on small, private trackers with exclusivity, speed, and quality as the main guidelines. You can't just join them either, most require relatively decent speeds tests, high ratios for seeding/sharing and have closed registrations, only invitations. Seedboxes are all the rage, and the hardcore pirates are probably using Usenet quite a bit now as well.
Get with the program granddad!
As you might now The Pirate Bay and piracy have been huge in Sweden. Spotify have changed that when it comes to music. By making it _easier_ to listen to music via their application than via bittorrent/kazaa/napster/dc++ downloading, they're now the most used music player in Sweden. Just a few years ago the Pirate Bay top 100 list was full of music. Now there's two (2!) music albums on it, the rest is tv-series and movies.
If you look at it that way, that piracy is the competitor not cd sales, the music industry has a great opportunity in Spotify in the long run.