Matt Cutts, Google’s SEO czar, passed along his answer to that question. The newspaper was selling links:
In Google’s world, we take paid links that pass PageRank as seriously as Amazon would take paid reviews without disclosure or as your newspaper would treat a reporter who was paid to link to a website in an article without disclosing the payment.
A good reminder of the danger of those “Partner Links” sections you sometimes still see on news sites: Once Google finds out about them, you can enter a world of pain.
— Joshua Benton