I think you might see some interesting results using a non-parametric [one that doesn't require specifying the number of clusters apriori] clustering algorithm, like mean-shift. I've never seen an adaptation for discrete data like this, but it should be possible.
You could have the same tradeoff between note-distance and time-distance.
Actually I was curious enough about this novel use (and I happen to be interested in music myself, who isn't) I saw your post and thought about replicating it and emailing you results. I'd be more than happy to work with you on any non-commercial stuff. (An email address which works for me is on my HN profile, could you send me a note? Even if nothing else it doesn't make sense for all of us to spider/scrape the same datasets over and over...)