I've had quite good results with AT&T's unlock procedure for our family's post-contract iPhones including a 3GS, 4 and 4S. So I was surprised when I was unable to unlock a phone that I thought was post-contract. I entered the number into AT&T's form, and before I could even enter the IMEI that identies the phone I got an inline message telling me I couldn't do the unlock.
It didn't explain why, so I was a bit frustrated. After I took stock of our phones and used AT&T's obscure contract expiration page I realized it made sense. With various swaps of phones and contracts among the family I'd gotten confused. We have five devices, 3 are unlocked, and we have two 2yr ongoing contracts for the newest phones (a 4S and 5). So I need to wait another month. 
If you're confused by this process (who isn't?), it helps to know AT&T's first test is by phone number. The phone number is the unique identifier for a contract. If that number has no eligible IMEIs associated with it then you can't go further (as far as I know).
If the phone number has eligible IMEIs then the next test is IMEI. I'll find out in a month how that works with a device that's been services swapped ... twice (... because the first Apple Store service swap (refurb) was defective of course).
 AT&T allows you to get a new contract phone prior to contract expiration, but that doesn't mean you get to unlock the old phone early of course.