" I think the problem is the way the searches work, since they are fuzzy-searches on each letter triplet, that you would need to type too many letters to complete your search. The goal of the search interface was to reduce the number of keystrokes, not increase them. "

I don't think that this would be much of a problem. Let's say you need to enter on average four letter triplets to find your song. I think it will be rare that those four triplets map to a song that you weren't searching for, especially since your only searching for either the artist name or song title, not both at the same time.

Also, like other people have mentioned, the substring search matches could appear after the normal matches. This would be useful, for example, your songs aren't very well organized (like me). If you can't remember the beginning of a song title, it would be nice not to have to browse through (up to) 60 gigabytes of songs to try and find it.