I went through similar hassles as the OP around the time the iPhone came out, during the 3rd week of June. My iPad arrived at the same time, and I couldn't get through at AT&T at all. Finally I did, and they told me to just sign up for the 2 GB plan for now, and they would change it manually to unlimited within the next 10 days.
I had to go to Europe immediately afterwards, for two full weeks, and when I got home, my plan was still 2 GB. So I called AT&T back, and they had it all fixed about 10 minutes later. No pain, no hassle. So I'm on the unlimited plan now, and I'm very happy.