Musical Similarity

Certain musical tasks (like automatically generating iPod playlists given a few musical examples) benefit from an ability to judge similarity between songs. But it's not at all clear what attributes make two instances of music similar. Listen to snipptes of My Favorite Things (Rodgers and Hammerstein) performed by several artists. They're all the same song. But are they similar? How are they similar? How are they different?

The Melody (see score below) [MIDI]
Sound of Music (Julie Andrews) [mp3]
John Coltrane's version (notice that the 3/4 meter becomes 6/8) [mp3]
Barry Manilow [mp3]
The Supremes [mp3]
Sarah Vaughan [mp3]
Dave Brubeck [mp3]
Outkast (like Coltrane. Sampled?) [mp3]