We know that the network is overloaded in condensed areas. I think we can all agree that tethering won't do anything to decrease the usage of 3G, so in a way, yes, they have some proof. I still feel that they need to present facts about network usage in regards to tethering, specifically.
The user base is constantly growing each day with every new subscriber. It's not as if network usage is at a standstill and AT&T must only accommodate for the current situation. They need to consistently make improvements to the network for this reason, alone. The question that still remains is if the enabling of tethering for iPhone users will push the network beyond what it can handle, given that its demands are growing, anyway.