I have read this message board from start to finish and am so glad to hear that I am not the only one having an issue.
I had an iPhone 3GS and went to the 5 on AT&T Tuesday night. On my way home I noticed that I couldn't access the data network. AT&T support had me power cycle the phone and I now had "4G".
The next day I had to go to an area that had no service. When I regained coverage, my signal bounced from AT&T E to AT&T but no 4G. When I got back to my desk and power cycled the phone everything worked again. Later that afternoon, I had to go back to the site. This time when I regained coverage, I had only AT&T but could not make a call and surf the internet at the same time. After about 45 minutes the phone read 4G.
I have swapped the sim card and reset network settings multiple times to no avail. In a final act of desperation, I switched to an iPhone 4S. The new phone needed to be upgraded to iOS6. While driving home I lost reception and again could not get 4G back.
One difference was that my camera App would not let me switch to record video. I reset the phone completely and now have better service than I did before.
I don't think the issue is in iOS6 as my 3GS was also using it. My thinking is that the new hardware is having trouble switching from an EDGE tower to another tower.
I certainly hope Apple gets these issues resolved.