I have been looking at a couple music recommendation services that some friends pointed out to me. Music Plasma is quite visually interesting, with its planet-like display of bands and their relationships to each other, but it definitely needs more information (many bands don't have their albums listed, and not enough bands are in it).
Audioscrobbler is more interesting and I have signed up for it to see what recommendations it produces. It uses plugins for your music player to track what you are listening to and eventually give you recommendations based on some kind of matching scheme with other listeners. It will also set up a personal internet radio station for you based on your listening patterns. It is free, and they don't really collect any personal info except what songs you listen to.