I *just* did this.
First email sent to AT&T on 23 September, and got confirmation same day, saying 5-7 business days.
Got email on 30 September saying it was reviewed and approved for unlock, and to wait 24 hours from that email to complete the unlock.
Today, 15 hours after the second email, I put in a new SIM card from O2-UK, and it works. I didn't have to restore it with iTunes, and I never got the message that says, "Congrats, your iPhone is unlocked." I did check the IMEI sites, and they all show my phone is unlocked, so I know it's all fine. I even shut it off and restarted a couple times and synced the iPhone with iTunes just to make sure it all works right. I can play my music via iTunes Match, still on 5.1.1, and it's just like normal. No jailbreak or any hacks.
So in my case, from my first action in emailing AT&T to fully unlocked iPhone, it took eight days.