From your mention of the firmware, it appears that your iPhone
had been previously hacked or jailbroken to use with a carrier
other than AT&T. If this was the case, such unauthorized
alteration frequently prevents a later legitimate unlock. Did you get
the "Congratulations. Your iPhone message is unlocked" in
iTunes when you followed AT&T's instructions after your
request for unlock?