I just installed iTunes 8 with the new Genius music recommendation/playlist feature. I have played around with similar functionality for years in the form of Pandora and MusicBrainz. These tools are how I find new music anymore (combined with iTunes own recommendation system and Amazon's recommendations). I have not listened to the radio in a few years at least.
Genius is pretty cool when it works. It instantly generates a very mood appropriate playlist from a selected song, which is nice. The Genius side bar shows a whole bunch of recommendations too - this function blows away the old school iTunes recommendation system since it allows you to look for specific kinds of music.
But it completely fails on obscure tracks and obscure genres. Even on obscure tracks and genres purchased from the iTunes store. It is useless for classical music, usless for traditional irish music, usless for some classically influenced electronica (where useless is defined as not recognizing a large enough fraction of similar songs to build interesting playlists, not as the complete inability to recognize anything at all). It doesn't work for music videos at all, unfortunately, either (come on Apple - that should be easy to solve for videos purchased in the iTunes store).
Still it works for some surprisingly obscure stuff and it is wicked fast. I'll definitely be using it.
But if you find yourself getting the message, "Genius is unavailable for the song..." frequently, do yourself a favor and install MusicBrainz.
P.S. I have also discovered that it works differently for music purchased from iTunes vs. other music. Even if the tracks are identical otherwise (different formats, but the same sound signature).