Qwest wouldn't give the NSA all their call data records, and neither would T-Mobile USA. The why, from ThinkProgress: the fine in the event of successful legal action would be $1000 per violation, and with a multi-terabyte database of records, each one a few bytes, that's a lot of money even to a monster telco. Qwest has 14 million subscribers or thereabouts - even if they just made one call each, that would be a downside risk of $14 billion, or twice that if they called fellow-subscribers.
Assuming realistic usage figures, it's not so much "a billion here and a billion there and soon you're talking real money" as "a hundred billion here and there and soon you're talking all the money in the world." That doesn't explain the others' decision to cave, though.
Defense Tech has two interesting social-network diagrams, one from a large company, one from Al-Qaida. Can you tell which one is which? Key implication: putting more data into a stupid analysis process probably has negative returns.