CNN

Attorney General Alberto Gonzales testified before the Senate Judiciary Committee on Tuesday.

WASHINGTON (CNN) - A report Sunday by the New York Times said a new disclosure could help clarify one of Attorney General's Alberto Gonzales' statements, which has fueled a controversy over whether he should remain in office.

But on Sunday political talk shows, prominent lawmakers from both sides of the aisle showed no sign of backing down in their calls for his ouster.

"He doesn't have much credibility, and he would do us all a favor if he stepped down and allowed the president to select someone else," Rep. Christopher Shays, R-Conn., told CNN's "Late Edition with Wolf Blitzer."

"You need to be truthful to Congress. You can't be inaccurate so often. Finally there just builds up this incredible credibility gap."

Gonzales' apparently contradictory statements, repeated use of "I don't recall," and refusal to answer many pointed questions in testimony before the Senate Judiciary Committee have contributed to calls for his ouster.

On Thursday, four Democratic senators called for a special prosecutor to be appointed to investigate whether Gonzales committed perjury.

But President Bush has said he maintains faith in Gonzales, and Sen. Orrin Hatch, R-Utah, predicted that the attorney general will tough it out. "I have a lot of respect for the man; he's willing to hang in there," Hatch told ABC's "This Week."

The Times story focuses on the National Security Agency's once secret surveillance program - computer searches through electronic databases that identified the senders and recipients of millions of Americans' e-mails and phone calls, though not their contents. Current and former officials told the Times that that part of the program triggered a dispute within the Justice Department about its legality.

Bush had publicly disclosed that an NSA program included warrantless eavesdropping on phone calls between people in the United States and suspected terrorists overseas - but he has never publicly disclosed the existence of the data-mining program.

Last Tuesday, in testimony to the Senate Judiciary Committee, Gonzales said a dispute among top Justice Department officials in 2004 - which prompted an emergency meeting with congressional leaders at the White House and a late-night visit to then-Attorney General John Ashcroft in his hospital room - was not about the NSA surveillance program Bush had disclosed. Rather, he said, it was about "a very important intelligence activity," which he would not detail.

"The disagreement that occurred, and the reason for the visit to the hospital ... was about other intelligence activities," Gonzales said. "It was not about the terrorist surveillance program that the president announced to the American people."

But on Thursday, FBI head Robert Mueller appeared to contradict Gonzales. Mueller said Ashcroft told him shortly after Gonzales left the hospital that the meeting had indeed dealt with the "NSA program that has been much discussed."

Also, a document prepared last year by the office of then-National Intelligence Director John Negroponte lists briefings given to lawmakers on the NSA surveillance program. A March 10, 2004, meeting at the White House is on that list, despite Gonzales' assertion that that meeting had been prompted by different "intelligence activities."

The Times reported Sunday that, since Bush has never publicly disclosed the data mining, Gonzales may have been drawing a line between the eavesdropping - which the president had announced to the American people - and the data mining.

"If the dispute chiefly involved data mining, rather than eavesdropping, Mr. Gonzales' defenders may maintain that his narrowly crafted answers, while legalistic, were technically correct," the Times wrote. But the article added that "members of the Senate Intelligence Committee, who have been briefed on the program, called the testimony deceptive."

Sen. Chuck Schumer, D-N.Y., a member of the committee, did just that on ABC's "This Week."

Schumer said "many on the intelligence committee," including three senators who have joined him in calling for the special prosecutor to investigate Gonzales' remarks, have noted that the phone and data mining are regarded as part of "one and the same program."

"It's just one program" with "separate parts," he said.

Other Democrats also showed no sign of backing down against Gonzales.

Rep. Jane Harman, D-Calif., told CNN's "Late Edition" that she was in the 2004 meeting in which lawmakers were briefed. "And I know only one program was at issue," she said.

Suggesting otherwise is a "slippery slope, and the chief law enforcement officer needs to tell the truth," she said of Gonzales.

Sen. Patrick Leahy, D-Vt., the Democratic chairman of the Judiciary Committee, said, "I think a lot of us, Republicans and Democrats, were incredulous at some of the answers" Gonzales has given the committee.

"I told him, frankly, I don't trust him," Leahy told CBS' "Face the Nation."

The committee gave Gonzales a week to correct his testimony, said Leahy. "I'd suggest he consult with a lawyer as he does it."

Leahy added, "Frankly, at this point, the president ought to take a long look at this and ask, does he want to go down in history with this attorney general as part of his historical record?"

The committee's ranking Republican, Sen. Arlen Specter of Pennsylvania, said Gonzales should step down. "There's no doubt, as I have said repeatedly for months now, that the Department of Justice would be much better off without him," he said.

Specter noted that he and Leahy have "never been read into the program," despite Specter's efforts as chairman to receive a full briefing. "And we need to know precisely what there is to the program. There have been some suggestions in the last couple of days that there may have been a separate facet of the terrorist surveillance program."

Hatch said Gonzales has "done a lot of good things" at the Justice Department and said he has been "used as a punching bag by the Democrats and, I might add, some Republicans."

Gonzales faces numerous questions about his honesty and his awareness of what has happened in his own department. The committee's investigation originally began as a look into whether some federal prosecutors were fired for political reasons.