Sounds perfectly plausible to me. And a June 7th article fits well with the time line--Gonzales claims his staff "corrected the record" to Eggen two days after the inaccurate press conference, which was held on June 5th. Whether this is perjury in a legal sense is anybody's guess, and may hinge on the technical accuracy of Gonzales' contention that the two different versions of the TSP actually constitute two different programs. That he sought to mislead both the press and the Judiciary Committee, though, is abundantly clear, and it makes the "definition of 'is'" business from 10 years ago seem like an example of crystal transparency.
I think you leave out a possibility (the one I think is most likely), i.e., that Gonzales was just being hyper-legalistic here. When he refers to the "Terrorist Surveillance Program," he's referring to its current incarnation, not the pre-2004 version of the program that James Comey refused to sign off on.
When Comey and the DOJ objected, the program underwent serious revisions. Thus, "the program the president confirmed" in 2005 is actually the new and improved program, not the program that everyone objected to in 2004.
As for the "clarification" that Gonzales supposedly communicated to Dan Eggen, I think I found it. It's buried toward the end of Eggen's June 7th article:
Justice Department spokesman Brian Roehrkasse said the surveillance program "was always subject to rigorous oversight and review. . . . We have acknowledged that there have been disagreements about other intelligence activities, as one would expect."
It's pretty clear from the article that Eggen had no idea what that was supposed to mean, but included it anyway. As the rest of the article makes clear, Eggen was still operating under the assumption that the program Comey was talking about was the TSP.