I think there's a good reason it doesn't do a full substring-search: If it did, you'd get too many search hits and you'd have to press too many letters to get to what you wanted. As it stands right now, you can usually find the title or artist you're looking for with three or four letters. If they made it a substring search, it'd be more like 6-10 letters. Since this is meant to be used in the car, they have to make it as few keystrokes as possible.
I disagree, I think. If it added substring matches down the bottom of the list, then you wouldn't care about all those false positives, because you'd never see them, unless you wanted to. It would also fix the case of when you're searching for a song, but you've forgotten about the first word. At the moment if you're looking for "Back to Mother Earth", and you search for "Mother Earth", you get nothing. If you add all substring matches at the end, then you get no UI penalty (the existing button presses will still work) but you get a benefit (now you can select tunes with substrings). There may be a performance penalty, though.
I've held off on this comment for a while because Hugo keeps saying things like "In the next revision, the whole searching / playlist ui will be completely revamped, and you'll love it". Perhaps this will do a lot towards addressing all these issues.
Richard.