FWIW- I was an existing Cingular/ATT customer 'upgrading' to iPhone. Attempted activation @ 7:30PM EST last night, got the 'additional time needed' message / email.
Called AT&T around 10PM ET last night, said everything looked ok on the account, it may just need a little more time. Gave up for the night. Check this AM at 6:30, still not working, no email. Called the Activation # again at 7AM when they opened, again said all looks ok, but would have someone call within 30 mins to help sort this out. 2hours pass, so I decide to go to the local company owned (very important, resellers cant help) store.
After the rep there calling several numbers, and 75 mins, and trying everything they could think of on the phone and in their billing system, they finally asked her to swap the SIM out (had to show her how) and send me home. Fortunately I had brought my laptop and the sync cable, I told her I did not want to leave until I was activated. Got iTunes running, went through the process again, and within 3 mins the phone was working!!
This may not work for everyone, but a SIM swap sure saved the day for me. I'd also bring your laptop if you have one.
Other reps were sending iPhone customers home and telling them to call the activation number - so be firm, and let them you already tried that route.
Hope this may help a few of you..