Apparently the secret to getting your iPhone activated as soon as possible is to leave it plugged into your computer and connected to iTunes until activation is complete. A support person from AT&T told me that the their system works by going through a queue and pinging every unactivated phone in turn to activate them. If the system can’t see your phone, you lose your place in the queue and have to wait for the next time.
Those of us trained by the iPod are in the habit of disconnecting from our computer once the sync is complete, but when it comes to iPhone activation don’t do that. Just plug in the dock and wait.
Bottom line, my phone still isn’t activated and it’s probably my fault. My own knowledge confounded me this time, since I was working under the assumption that when you plug your phone in it polls for activation info from AT&T. I kept power cycling it and disconnecting it from iTunes, and have an unactivated phone to show for it.
Update: This tip may work, but I had to call support again to get my phone activated.