Just an update to all I got mine working!... I sat with my phone "Waiting for AT&T Activation - This may take some time." for about 4 hours. Rebooting the phone did not help. Removed the SIM & re-inserted without any luck. Called AT&T twice, Apple twice, no help...
Finally, I called AT&T and said that I'd done the iTunes activation, the phone was unlocked but "waiting for activation." I explained that Apple had said the hold up was on AT&T's end. I lied and said Apple told me to have the IMEI # checked... she looked over my account, made a "hmm" noise, and said, AH - your phone should be active now. BAM - It went from No Bars/No Service to Full service and AT&T. I asked what was wrong, and she said there wasn't an issue she just was going to re-send the activation signal.
The number I called was 1-877-419-4500
Give them you iPhone telephone number
This will probably only help those of you who are getting the message "Waiting for AT&T Activation - This may take a while"
Good luck!