Call ATT technical service. ATT now unlocks all phones that are beyond their contract (All 3GS are beyond contract by now). All you need is the IMEI number (can be found in settings) and they will notify Apple to unlock your phone. All you have to do is to restore your phone via iTunes. It usually takes ~3-5 days until they unlock it. Worked like a charm for me. At that time I had already a iPhone 4S running on the ATT contract however ATT still was able to unlock the old 3GS phone.