For the "coldplay" problem you may want to use an inverse band frequency weighting (much like in IDF for text). Bands that are extremely popular won't give you any useful signals. As far as the cold-start... yep, that's a beast and using social data may help. For example, are you using stuff from Facebook/Twitter once you have users sign in? You could crawl out band/artists name from their data.

This gives me an excuse to try grooveshark. I've been curious for a while. :)

update: I didn't see any recommendations based on what I've like on Facebook or Twitter. This would be a good "warm" start. Note: I'm working on stuff like this, but don't mind sharing this simple idea. :) Quora does a great job of this pulling in data from your Twitter network.