For one, I would have made the awesome-bar return some search results as well, and made it impossible to distinguish between those and the bookmark results. They could also have compared auto-completes against whitelists/blacklists.
If you have a multi-billion dollar budget to test every pixel of the user interface then fine, but what if you're an indie developer and have to do with a budget of $100?
The "cheep" way to do A / B testing is for B to always be the existing system. Roll out changes to 10% of your users and see how they respond. Just remember if your users hate it then fix the problem and test it again or abandon the idea. So, this only works when you can measure how they resound to changes.
Also a UI change can get more plaudits by virtue of the placebo effect, IMO (I've not done double blind tests!), making things appear better simply cause the look has changed.