Nothing has changed since the inception of locked mobile phones. Only the carrier can unlock them and you must meet their requirements.
AT&T will ONLY unlock iPhones for current customers in good standing.
Unless you specifically bought an unlocked iPhone (paying full retail has NEVER meant unlocked) then you are most likely out of luck.
Apple can not unlock it for you. Only AT&T can. They require that you be a current or former customer in good standing and that you either completed your contract, paid the early termination fee, or purchased a no commitment phone.
Since you were never an AT&T customer, they will not unlock it for you.
I contected at&t again via the live chat at http://att.com/global and now they told me to call 001-916-843-4685. The girl asked me a for the imei number and some general info, and my phone should be unlocked after a week or so.
I bought a locked to AT&T iPhone 4 almost two years ago, but paid the termination fee right away, and have been using it with T-Mobile since. This, of course, has always required unofficial unlocks .
I was very happy to read it's now possible to get an official unlock for accounts in good standing and contracts fulfulled. So I called AT&T two days ago and requested an unlock. For some reason, it was not possible to do right away - probably my situation was unusual, with the termination fee, instead of two year contract completed.
Anyway, today I got the official reply from AT&T - and they wrote "We have reviewed your request and confirmed that you are eligible to have the requested iPhone unlocked." ::))
Sadly it requires a full backup and restore.. Even though these instructions:
http://support.apple.com/kb/TS3198 say the unlock should just happen when connecting to iTunes. It does not - even with the original AT&T sim. Well, just have to try restore, but that will have to wait a while.