Size and egregiousness, I think. There are worse offenders, and there are bigger companies that play fast and loose with SEO, but this is the biggest company to do something so black-hat.
How was it detected? Just noticing Penney seemed to be ranking awfully high in a lot of searches, or something else? (I ask because the blackhattery mentioned in the article didn't seem very noticeable in its own right.)
I actually figured out what the basic strategy was, but Doug dug up a ton of data on exactly what they were buying. Some of it is kind of insidery stuff you'd want to know if you were an SEO but not if you were a typical Times reader. (David Segal does a really impressive job in general of writing about this stuff in a way that's understandable to the average person. I hope he does an article about white hat SEO some time, so I can cite it when I explain SEO to my clients.)
It may be more black-hat than some attempts, but the most frustrating thing about this article is that it implies that paid links are a rare thing for e-commerce sites. Pick any shopping-related term, and the odds are overwhelming that the top-ranking site has a large SEO budget.
Agreed, if the average-user only knew how prevalent this is. We're an e-commerce site and constantly feel in the minority for not buying links exactly like JCP did. Almost all of our top competitors do the exact same thing and have gotten away with it for as long as I can remember. The only reason we don't is being too afraid of the supposed "wrath" that doesn't ever seem to come to them (that is unless you can get a NYT article written about it).