Google's offers to Android OEMs often mix search revenue, app store revenue, and ad revenue... a tying nightmare. Google is now under significantly increased scrutiny for how they manage these deals, they've gotten in trouble for destroying evidence and will now have even more incriminating evidence for future arrangements... it's a great time to press Google for a better deal because their hands are tied.
In the past Yahoo, Bing, Yandex, etc. have frequently gotten outbidded by Google for similar deals.