I filled out the AT&T unlock form (see post #2, above) for three iphones that we upgraded on launch day (a 3GS, and two 4S).
I had the unlock confirmation for two of them within about 30 minutes, and the third one in about an hour. All of them now give the "congratulations, your phone has been unlocked!" message in iTunes when Restored.
No charge for unlocking through AT&T, but they will only unlock out-of-contract phones (with an exception for active duty military on overseas deployment).