Seemed fine enough once I started getting results, but I'd center/leftify the search box and make it search-as-you-type because you're filtering on a known set of data.
My UI is terrible, I know. "Leftify" is a great term, btw. Do you think it's visible enough from the header, or should I move it down?
As for "known set of data," the query language is a full, SQL-like language (including compiler to SQL). This is another issue with the search-as-you-type, but compiling an 80-character (ish) search and getting a few results back should be quick and easy, so I'll see what I can do.
Also, did you notice the sorting option, or was it too hidden?
That's what we do, and we have millions of names to complete: http://www.trailbehind.com
Here's the YUI library: http://developer.yahoo.com/yui/autocomplete/
I can send you the code for my autocomplete widget if you want. Email me at andrewljonson [at] trailbehind [dot] com