I think the biggest problem that Google can't fix is that they treat links as a voting mechanism, and that voting mechanism has value. So, there is a big economic incentive to "buy votes" by buying links. As long as there is a financial incentive to ranking well in google and that the mechanism to rank better is to get links, people with money will buy links in the same way they buy influence in the media, politics,…
Google punishes people that buy links, just like our government punishes people that buy votes. That sets up an incentive to not do it. I would say, this problem is not in the "can't fix" category. Just like in real politics, Google must tread carefully. You can't arrest the president because someone bought votes on his behalf, just like Google can't nuke a site because it has purchased links.
The incentive doesn't disappear, as there is a great deal to be gained by being bumped up search results. They raise the costs or circumventing the system, but that just means people look elsewhere. Its an arms race.