I have been having the same problem over the last two days in Wilmington, DE and Baltimore. I think the 3G network is getting saturated.
I have found that turning airplane mode on and off, or turning the 3G radio on and off will get the connection running again, at least for a bit.
Hopefully they are building out their network and things will get better. Maybe we will start hearing about the "iphone effect"...
I think Apple admitted it had something to do with the firmware. The iPhone will avoid the 3G network if it's too saturated, but I guess with the explosion of iPhones, you're going to be lucky to find a 3G network that isn't full of iPhones. I'm pretty sure Apple is working on a fix by way of a firmware upgrade - at least I think I read that somewhere.