AT&T allows some customers to "unlock" their phones. This allows the use of a SIM card from a different provider (for example, VodaFone) while traveling. (It also allows you to use the phone with another GSM provider in the US after your AT&T contract is finished, which is one reason AT&T and other carriers lock the phones they subsidize.) 

I don't know exactly what makes a customer "eligible" to have a phone unlocked, but I suspect that you have to have made several payments on time and be in good standing. When I am under a new contract with a subsidized phone I typically wait a few months (in this case, about 6) before calling in to ask to have my phone unlocked. I've had T-Mobile unlock three phones (under 2 different contracts) for me in the past, but this was the first time I tried it with AT&T.  

I suspect that AT&T has an official policy of making it difficult to unlock your phone. Here is my experience:

On my first call (September 25th) the customer service representative asked for my phone's IMEI (a phone Specific ID number which can be found by entering *#06#) and put me on hold for ten minutes. After that wait, they confirmed that I was "eligible" for unlocking, and said they would send me the unlock code and instructions via email, with an expected resolution on the afternoon of October 3rd. (Yes, that's 8 days to look up the subsidy unlock code…) The entire call took around ten minutes.

Commentary: The process of retrieving a subsidy unlock code using an IMEI should take all of 1 minute if the customer service agent had access to the database. If they had to submit a ticket for a higher level  technician to look up and return the unlock code it should still take only a few hours. The only reason I can think of for delaying at this point is to hope the user forgets about asking for the unlock code.

Nine days later, I had not received an email with the unlock code, so I called AT&T back on October 4th at 6:18pm. After spending a few minutes on hold waiting for a customer service representative, I was connected with Louise. After I had explained why I was calling, she asked if she could put me on (silent) hold, and I sat on the line for six minutes before she came back, apologized for the delay, and asked if she could put me on (silent) hold again, which lasted another 8 minutes before she came back on the line. At this point she gave me the subsidy unlock code (an 8 digit number) and the instructions for using them. [Insert a foreign (non-AT&T) SIM card, enter the number.]  The entire call took 24 minutes.

Commentary: Either Louise (and AT&T's customer support system) is terribly slow, or the two (6 and 8 minute) holds are designed to make the customer give up before their phone is unlocked.  The wait time was longer than with T-Mobile (although I also had to make a 2nd (follow-up) call to T-Mobile on one occasion.) All in all getting a phone unlocked is annoying enough to prevent people from doing it casually, but not quite difficult enough for AT&T to get hit with a class action lawsuit.