It's worth noting that the principle of the thing is not nearly so simple. The government may claim that they're only interested for anti-terrorism activities -- but check out this article on ZDNet, put that together with the phone record thing, and follow the logic through.
These phone records can be used to figure out who has been talking to reporters, at least if they use the major telcos. Given that information, those people can be much more effectively suppressed, thus quietly removing the main mechanism by which the American people find out what the government is doing these days. By the government's frequently stated logic, these media reports aid terrorism. (I personally find this logic to be largely rubbish, but they've been saying it over and over again in recent months.) Therefore, by the administration's standard arguments, it is not only legal but necessary to use those phone records to track down and squash whistleblowers within the government.
Now are you worried? Yes, it's an extremely effective tool. That's precisely why it requires rigorous oversight, not just permission...