But soon after Penney made the Martha Stewart deal, Macy's sued, claiming exclusive rights to her branded goods. Also going sour were other Johnson moves: ditching store brands in favor of national ones, abolishing coupons, and drastically rebuilding or renovating stores. His strategy cost billions, as a company that had rung up $17 billion in sales the year he took over collected just $13 billion last year.
Today, with the holidays just around the corner, the aromatic olive oil is gone from Penneys, as are other Martha Stewart Pantry home goods, and Johnson himself - sacked in April after 18 months. The activist investors who had brought him in also cashed out and went home.
Penneys executives are trying to slap meat back onto the carcass of one of America's oldest retailers just as holiday decor and deals should be the stars. Instead, the biggest glow on the sales floor seems to be the spectacular corporate flameout.
I got a glimpse a few days ago while walking through a Penneys I had written about a year ago when it opened, at Willow Grove Park, as a 120,000-square-foot testament to Johnson's vision for what all stores would one day look like.
Thin with buzz, customers, and sales associates at midday, the store felt like a place with a muddled identity.
All around were signs - literal and figurative ones - of the intense regrouping under way under onetime and now-returned CEO Mike Ullman. Sale signs were abundant again on merchandise displays, replacing Johnson's "fair and square" pricing attempt that went nowhere with Penneys customers accustomed to the rush of a markdown.
Given prime space again on the sales floor was St. John's Bay apparel, a much-missed brand during the Johnson experiment. And some of it was on sale for "50 to 55 percent off," to boot.
In the home-goods aisle, there was no sign of that delectable olive oil. When I asked a sales associate to point me to Martha Stewart home goods, she asked a supervisor, whose response was a matter-of-fact: "We don't carry that anymore." The decor was spare, the inventory clean-looking, but devoid of the abundance that can make holiday-season department store shopping a treasure hunt.
In trying something new, Johnson was looking for a way to reposition Penneys for a long-term future, rather than watching its sales wither in an increasingly crowded field of competitors such as Macy's, Kohl's and Target.
But even Macy's stumbled after the financial crash of 2008, only to come back hearty and healthy and with its stock doing well. The fruit of Macy's success was evident that same day at its store in Willow Grove.
Almost every square inch of floor space was characteristically jammed with displays, desired and defined merchandise, and the retailer's trademark red logos and lush holiday decor. There were customers, even on a weekday, and a bustle and buzz. Just a few paces past the threshold there was no doubt: You were in Macy's.
Johnson is credited with the Apple Store - a clean space that wows vistors with Spartan displays that let the company's diabolically attractive smartphones and tablets shine. At Penneys, Johnson was working mostly with replicable apparel and other merchandise. No patented touch screen, no industry-leading tablet technology, not even a legal lock on Martha Stewart-branded home goods.
Driving home the extent of his Penneys failure was this scene at the Willow Grove Apple Store: Full of customers and associates; iPads mounted next to iPhones, so customers could scroll the tablets for information about smartphones on display. Squat tables labeled "kids" with iPads there for sampling. Products selling the product, and the store itself, actually, beside the point.
Penneys has a lot of ground to recover. It may even be impossible. But with any luck, at least the worst of the voodoo may be behind it.