What does “We don’t do anything that’s not completely up and up” mean?

I found an amusing story titled “Lobster salad, but a key ingredient was missing” in today’s (August 11）New York Times NY/Region section.

The article reports that Zabar’s, the famous grocery in Upper West Side, have being selling “lobster salad” at $16.95 per pound for years. The only inconvenience being that the main ingredient is crawfish, the salad itself doesn’t contain a single bit of lobster meat. It has long been a very popular grocery item with New Yorkers.

When the secret was betrayed by a reporter of The Times-Picayune of New Orleans, the news spread quickly to local newspapers. Saul Zabar, the 83-year-old president, insisted that selling lobsterless lobster salad was not dishonest at all, citing the case of a Japanese version of crab meat using pollock as the base, widely sold in Japan under the category name of “Crabmeat Resembling,” – which caught my eye on this particular topic.

Cutting to the chase, the following phrase caught my attention, “We didn’t think that we were doing anything that was not completely up and up,” in the following remark of Mr. Zabar:

“But by then Mr. Zabar had had enough. “We really didn’t think that we were doing anything that was not completely up and up,” he said, “but there was an element that might be confusing, and with all this stuff going on, I decided now’s the time to clarify.”

Eventually he changed the name of the product.

What does “completely up and up” mean? Is this a common, colloquial phrase?

I believe the phrase you're asking about is normally "completely on the up and up" which means to act in adherence to the rules (such as laws and regulations); the use of the word "completely" implies a strict adherence [to these rules].

When a person (or organization) is not following all the rules in their activities, then it can be said that they're "not operating on the up-and-up" (although "under the table" may be a better fit in many of these scenarios).

"On the up and up" is the usual phrase, to indicate entirely honest and straightforward. This isn't quite the same as obeying all the relevant rules and laws: it's something more. Finding loopholes, obeying the letter of the rule rather than the spirit, and hiding something in the small print are all legal, but not on the up and up. So Mr Zahar was saying that he was certainly not doing anything wrong, and didn't think he was doing anything unusual (until it was pointed out to him).