You could probably still do it. These guys aren't so far along that they're unbeatable. Just look for a chink in their armor. What's missing or broken in the way they're doing it?
Amie Street isn't perfect. It's a beautiful idea, but it didn't work for me the first couple of times I've visited (I use Linux, so I pretty much expect websites to not work, if they do anything fancy...I just move on). This post caused me to check it out again, and the player does work now. Hooray!
Executing better is still a possibility. Niche-focused versions would also be a possibility. Most of the top ten on the front page suck. I've been a happy subscriber for years with eMusic and it's focused on indie music (I guess Amie also has a focus on indie, since no one else is taking part in this model right now, though the number 1 song at Amie right now is atrocious "soul" pop).
Someone already thought of MP3 players before the iPod and search engines before Google. Someone else in the market should be encouraging, not discouraging.
If they are doing it REALLY REALLY well, you have lots of options (which are laid out pretty well on that gobignetwork post).