The biggest change in their redesign has nothing to do with the new logo, redundancy in navigation (because that can't be an issue) or making the different search tools more discoverable. The biggest change is the top left position of the first search result relative to the top left position of the document. In other words, the average scanning pattern has completely changed with the addition of a fixed side bar. It…
Edit: These images may support my contention: http://www.google.com/images?q=google%20results%20eyetrackin...