I actually don't mind the fixed header on the current version because it is much smaller and less obtrusive than the header on the redesign. I dislike fixed headers on news sites like the New York Times, because I want as much vertical space as possible to read the article. On a search engine, there is no issue of losing context, so a tastefully constructed fixed header is acceptable.

I understand why you wanted to add a second toolbar for more options and am not suggesting that you removed completely remove fixed headers for the default landing page. I just think that the second toolbar could easily fit on the same line as the search bar.