A shame, but as much as I love the iPhone, I don't love it enough to abide by AT&T's new pricing policy.
I would suggest it's time to try Android.
I'm an apple consultant and i work with iPhones almost every day, and hold several apple certifications, so don't flame me too hard; i'm as big a Mac fan as anyone. Apple's ongoing success is how I make my living. However, I'm also stuck with Verizon due to company stuff, so I recently caved and got an HTC Incredible.
Sure, you can find nitpicks about it, just like you can with the iPhone, but it's really not a bad device all around. I'm especially fond of the Google Voice integration; Google really one-upped Apple's visual voicemail with it. Also, you can easily get apps that allow tethering that bypass the "official" tethering service that Verizon charges for, due to the somewhat-more-open ecosystem. I also really enjoy streaming pandora while I'm driving to meet clients, so i appreciate that I'm contracted now for at least two years of an "unlimited" data plan at a reasonable (compared to new AT&T pricing) price. Verizon's soft cap is 5 gigs, and at $30/mo the same thing would cost $55/mo under the new AT&T disgrace.
Sure, I'll get flamed for saying it, but after using it for about a month, I'd rather have the Incredible than a Verizon 3GS if it existed, and I'd only really feel bad if a Verizon iPhone HD does turn up next week.
As for whatever comes out with AT&T, I used 2.5 gigs of data last month, and I'm only ever going to want to do MORE with my phone, not less. So the recent change in AT&T's pricing killed any chance of me ever switching to AT&T, no matter how great the new iPhone is. Good job, AT&T!
I know Verizon's probably going tiered too soon though, so who knows where we'll be when my 2 year contract ends. Sprint maybe?