Started happening to me after leaving the airport yesterday driving around South Philadelphia. Service was fine all day in Cleveland, though.
One of Apple's reps did tell me (and I posted this) that AT&T was going to be rolling outtages soon. Maybe this is what he was talking about. Perhaps there's a mass tower upgrade going on.
This is exactly what they told me last week when I started having major issues. I was getting no connection yet had full service signal.
When I phoned AT&T (and I posted this some time ago- even emailed arn about it) this is basically what transpired.
I told the rep I was getting no 3G service on my phone, spotty at best yet my signals were strong and my bars were full. I kindly asked him to see if a tower was down in my area, or if they were having problems in MI. He looked into the issue for me and his words Verbatim were : "Wow, oh, never seen this before" I asked of course what: he went to describe that the systems were indicating the the entire nation (Including Hawaii and Alaska) were experiencing issues.
He further went on to explain from the notes, that AT&T was doing some massive update due to the iP4 release, and they appear to have been behind with the update in correspondence to the release. He said to give it a day or so and report back.
I am continuing to have service (data) outages in my area, but it is working more now than it has been the last week or so. I cannot test my 3GS because I handed that down to my son who is on T-mobile; so I cannot speculate as to the service with the other iPhone's on the network.
Furthermore, I have no idea if this is phone related, service related, sim related, or a combination of all. I can say that I have not had the antenna issues others are experiencing. If I were to guess, it's the sim along with the transmission issues with the AT&T network.
Be that as it may, whatever the cause- it's pretty surprising (or not) that the only US carrier once again can't get it's act together on/before/after such a major product launch. Gotta believe this must have been a priority, yet here we are again, fixing it after the fact.