If it was purchased directly from Apple at full retail, it is. It it was purchased from an AT&T store at full retail, I don't believe they are unlocked.
I did a full restore on my phone after purchasing mine at Apple. (I had originally synced it at the store with iCloud.) Once I did the restore through iTunes, I got the "Congratulations your iPhone is unlocked" message. You could try a restore, but I think the key is purchasing at Apple directly.