It's google's success undermining the assumptions behind pagerank (!) leading it to perform less well.
Before google got so effective people put more work into maintaining collections of links to other sites; hand-curated omnibus directories like yahoo and dmoz or narrower fields.
As search became better this was increasingly a poor use of time; you could, after all, just go and google stuff to find it again, so why bother maintaining a hand-curated set of favorite links.
A consequence of this is that link-actions-taken-for-reasons-consistent-with-pagerank's-assumptions dropped, and reducing the signal-to-noise ratio insofar as pagerank is concerned; similarly link-actions-taken-for-reasons-contrary-to-pagerank's-assumptions increased (SEO), further dropping the signal-noise ratio.
Even extremely robust SEO-detection techniques can only cut away the increase in noise; now that people are less incentivized to publicly post high-quality hand-curated link collections there's less for the algorithm to go on.
This is why there's talk of twitter and fb vis-a-vis search; twitter and fb are where the info the search engines need currently lives.
(!) I know they use additional techniques these days but whatever they're throwing into the mix doesn't seem to be counteracting the overall utility decay.