The biggest problem is the lack of data about what people are searching. It's a catch-22 that's very hard to break in the face of Google's search dominance and ubiquity.
By Google being the best, it only becomes better, and introduces a huge barrier to entry to competitors. It used to be possible to know what people were searching for to end up in a given Wikipedia article, but the process is now only asynchronous (and limited) through Webmaster tools[1]
In my mind, the most interesting aspect of the announcement should not be how much money they have to spend, but how they plan on solving this paradox.