Just to add one thing to martinibuster's post and quote above, it seems, looking in hindsight, that Matt Cutts was referring to the then-upcoming Penguin algorithm (as the interview was in March of 2012, and Penguin rolled out in April of that year).
One part of that interview that seems particularly interesting to me is where Matt Cutts states:
"...and then we also start to look at the people who sort of abuse it, whether they throw too many keywords on the page, or whether they exchange way too many links, or whatever they are doing to sort of go beyond what a normal person would expect in a particular area."
So, since it seems highly likely that he was referring to Penguin, maybe there is more to Penguin than just bad backlinks? Maybe Penguin considers on-page factors as well?