So what happened that made the whole thing so egregious then? Why March 2004? Why not before?

The major thing that happened was Comey taking over as Deputy AG and Goldsmith taking over the Office of Legal Counsel. This was the first time the program had been up for review with these two on board.

I think Comey's testimony is revealing in this respect:

COMEY: In the early part of 2004, the Department of Justice was engaged — the Office of Legal Counsel, under my supervision — in a reevaluation both factually and legally of a particular classified program. And it was a program that was renewed on a regular basis, and required signature by the attorney general certifying to its legality.

And the — and I remember the precise date. The program had to be renewed by March the 11th, which was a Thursday, of 2004. And we were engaged in a very intensive reevaluation of the matter.

And a week before that March 11th deadline, I had a private meeting with the attorney general for an hour, just the two of us, and I laid out for him what we had learned and what our analysis was in this particular matter. [emphasis added]

The implication here is that not only was the legality questionable but that the factual basis of what they knew of the program was not adequate. Factually challenged usually means that someone has been lying, at least to the extent of not supplying all of the facts concerning the program. If Ashcroft had not been given the full facts and the full facts only emerged in the reevaluation when Comey came in as DAG and Goldsmith took over as head of OLC, that is sufficient reason for Ashcroft to change his mind about signing off on it. It has been noted on many occasions that the gap between what the executive does and what it says it does is sometimes staggeringly huge.

Another interesting point timeline-wise: This contretemps between the DOJ and the White House took place on March 10. Comey met with Bush on March 12 and Bush gave directions to "fix" the program so they could certify its legality. Comey said in his testimony:

COMEY: It was reauthorized on Thursday, March the 11th, without the department's — without my signature, without the department's approval.

And it was the next day — so less than 24 hours later — that we received the direction from the president to make it right.

And then we set about — I don't remember exactly how long it was — over the next few weeks making changes so that it accorded with our judgment about what could be certified as to legality.

And so it was really only that period from Thursday, when it was reauthorized, until I got the direction from the president the next day that it operated outside the Department of Justice's approval.

FEINSTEIN: For approximately two weeks?

COMEY: I don't remember exactly. It was two or three weeks I think that it took us to get the analysis done and make the changes that needed to be made.

Two or three weeks brings us to early April 2004 and it is worth noting that it was in April 2004 that Bush began going out of his way to say that his spying required warrants:

President Bush — April 19, 2004:

For years, law enforcement used so-called roving wire taps to investigate organized crime. You see, what that meant is if you got a wire tap by court order -- and, by the way, everything you hear about requires court order, requires there to be permission from a FISA court, for example.
http://www.whitehouse.gov/news/releases/2004/04/20040419-4.html

President Bush -- April 20, 2004:

Secondly, there are such things as roving wiretaps. Now, by the way, any time you hear the United States government talking about wiretap, it requires — a wiretap requires a court order. Nothing has changed, by the way. When we're talking about chasing down terrorists, we're talking about getting a court order before we do so. It's important for our fellow citizens to understand, when you think Patriot Act, constitutional guarantees are in place when it comes to doing what is necessary to protect our homeland, because we value the Constitution.
http://www.whitehouse.gov/news/releases/2004/04/20040420-2.html

It seems a reasonable question to ask whether Bush's sudden touting of the requirement for warrants in April has any connection with DOJ "fixing" the program shortly before.

And, of course, if fixing the warrantless eavesdropping was what was bothering Comey, Goldsmith, Ashcroft, and Mueller, then the dispute was about warrantless wiretapping and Gonzales has been lying his ass off.