A common misconception from carriers, they seem to think their lock only applies to one of the SIM slots on the phone, but they apply to both.

You have the choice of going through AT&T or there's the less expensive option of finding a shop / using eBay. Most of those will do it for about €10.