I wonder if you need to jailbreak it first. AT&T has unlocked two phones for me when I upgraded to new models. The most recent was a Motorola RAZR. It's possible, but not likely, that they might unlock an iPhone upon request.

EDIT: I had a typo. I had said that "Apple had unlocked two phones..."