JC penny probably got loads of publicity from the article. its not like their product was being slammed -- just the way they promote the website (which wasn't illegal, or even immoral. all they did was fall foul of one company's rules -- google.)
i think the interesting thing about the article is not what JC Penny did, but that the New York Times seemed to blindly accept google's position that these links were "bad".
to me, what they did was no different to a brick and mortar shop leafleting the neighbourhood. but google (and other search engines) have successfully drummed it into everyone that paying for a mention on someone else's website is not advertising -- it's something that should be punished.