The iPhone will be sending higher resolution pictures than other phones through the MMS network. It also will be sending video through the MMS network. Couple that with iPhone users' already exorbitant data usage and any network is going to be strained.
No carrier could even come close to handling the data throughput at&t is having to manage. Verizon could not handle this, they already have to cripple data services on non-iphones to reduce their network strain. Their 3G network is already proven to be slower than at&t's.
The iPhone hasn't been around that long and it's biggest modes of data usage (iTunes downloads over 3G, app downloads over 3G, youtube uploading) have been around for an even shorter time. The iPhone exploded faster than both Apple and AT&T could have predicted. Upgrading hundreds and hundreds of cell sites and nationwide infrastructure takes time. Mobile technology, particularly the iPhone, is advancing so fast it is a race to keep up for the phone companies. Verizon, so far, hasn't had to play this game to the extent at&t has.