We have redesigned our Real-time Search as well. A more contemporary design and more constistence with the homepage and our other products.
The default search order has been switched from popularity to recency. But you may still change the sort order it at any time.
Have a look and check it out at http://www.faroo.com .