They did get it wrong, and the problem has been well known for many months. Google has placed a weapon in the hands of anyone who wants to spend a modest amount of money to buy thousands of spammy links pointing to your site. But Google doesn't consider this a real problem, because you can spend hundreds of hours tracking these links down and disavowing them.
Google used to change the value of "bad" links to 0 rather than negative. The problem was that there was no risk to spamming. You might waste time, but you might get some links that Google didn't realize were spam.
There are a lot of problems with what srean suggested above, namely that it favors big brands who work with other big brands and creates additional barriers to entry for new companies.
I think Google has gone too far in link-based penalties, but the solution isn't to stop them altogether. Their current solution for weighing anchor text and trust is pretty weak. I've never seen a confirmed case of "negative SEO" working to penalize, but I have seen Google penalizing people for things that were not meant to manipulate the algorithm.
There's not an easy solution, but I think it's a far more sophisticated spam-fighting algorithm.
The problem is that spammers / extortionists can adapt their techniques much more so than Google can.
They care solely about getting paid, they don't care about building a brand, offering a good service or anything else. This allows them a huge degree of flexibility when finding ways to attack their less nimble adversary. They can transition from selling viagra to extortion with ease.
If it was straightforward, a company which employs many of the most gifted, technical minds in the world should probably have figured it out by now. Also, it's very unlikely that Pagerank is even in use at all at this point.
And stopping spammers is good - fighting web spam is (was) a major effort for e.g. forum operators.
This mass funelling of inlinks, also called a Sybil attack are not that hard to defend against if one tweaks the Pagerank equations just a little bit. The source of the problem in the original Pagerank equation was that it used addition. The Pagerank of a page was defined to be the sum of all inlink weights flowing in. Now sum is a problem because it cannot distinguish between links from a million shitty pages, from a link from a golden page if the total link weight flowing in is the same. I seriously doubt if sum is used anymore.
The solution is fairly straightforward, dont use a sum, use a function that weighs higher values higher. An extreme example would be the MAX operator. In this case, among all the inlinks my site receives, only the one with the maximum inflow counts, all the crappy inlinks might as well have not existed. Max is brittle though and causes instabilities in the convergence, but variations of soft max works decently enough in theory. To phrase it in another way, the original Pagerank equations used the L1 norm of the in-flow vector, one can use Lp norm [0] or fractional powers Lp norms with a higher p . If one chooses p = \infinity one gets the MAX operator.
[0] http://en.wikipedia.org/wiki/Lp_space#The_p-norm_in_finite_d...