AT&T cannot handle the current load on their 3g network as designed because of the iPhone users. Tethering iPhones only adds more potential problems. Its actually rather amazing that AT&T who owns most of the telco infrastructure at this point only allocates a walloping 8mbit standard spec of bandwidth to each 3g site. DSLAM's in major areas are usually allocated 155+ per RT. As to changing out a GSM radio for a CDMA one, there is usually not a problem; But in the case of the iPhone there will need to be some changes to battery / heat dispensation as the CDMA radios use more power than their GSM counter parts, as well as typically generating more heat. The iPhone tows the line as it is for both of those items, and 3g already ruins its battery capacity at least when using a 3gs version of the phone.
Verizon will have to wait till mid 2010 at earliest to even have a hope of an iPhone that can work on their network -- However verizon's allocated bandwidth isn't all that different from AT&T.. They simply do not have all the kids youtubing on their network from a phone yet like at&t does. Verizon's wireless infrastructure from what I know of it, will scale much better than AT&T's on that front; Long story short, AT&T had better do something and soon, because the iPhone is about all thats keeping them around at this point. However, when (and I say when because Apple is surviving on the iPhone / ipods and despite Steve Jobs tendencies of ignoring obvious money making positions, they do know what side their breads buttered on) Verizon gets the iPhone, they'll be in a similar boat as AT&T, however they should be able to plan better than AT&T for its success. Thus, MANY AT&T users are gonna jump ship when that happens.
My .02