I am surprised nobody else has chimed in on this thread yet, it really seems like a neat idea.

I was thinking about ways to get a larger datasource than the single song method you mentioned. How about scraping the "related artists" section of AllMusic or a similar site? Make a list of all the artists on a users empeg (or somehow select a subset of the artists), query amg for all the related artists (this would take a while). Build a rating system based on which related artists where returned the most times, and if the user does not already have music by that artist download some.

I guess this is similar to what you already outlined, but at the artist level instead of the track level. Plus this gives you the ranking across multiple samples instead of a single sample.

-Mike