THIS WORKED!
Here's my solution:
I did get the email from AT&T in no time after speaking to their tech support.
I did a mistake of backing up and restoring several times using right click at the phone icon in the menu on the left side. This just restores the settings.
I then realized that I need to restore using the button under the Summary tab -> Version section.
This downloads the latest iOS software and updates the firmware.
Even after this happened, I got no screen stating that my phone was unlocked.
I was disappointed and tried another trick, which FINALLY WORKED:
I took the SIM card out and did the same RESTORE.
This time it went till a point and then said I need to insert SIM to activate the phone.
I reinserted the AT&T SIM and then VOILA! got the popup message saying Congrats - iphone is unlocked etc...
Then it asked me if I wanted to restore from backup or just creat a new iPhone. I chose restore from backup.
It also asked me to register the iPhone all over again...
BTW, in the middle of all these, when I contacted Apple, they were quite curt and not helpful. Some of them claim to be "geniuses" to just boost their own egoes. They are actually quite clueless.
What truly happens is that AT&T sends a code to Apple servers saying that the iPhone can be unlocked. For your phone to actually become unlocked, the Apple servers need to be pinged. That happens only with the Restore button located under Summary -> Version tab. And of course, what happens after that seems to be a bit erratic... removing the SIM did the trick for me...
Hope this helps someone at least...