Someone may have more knowledge in this, but because it is unlocked, it might be a problem since you are not bound solely to AT&T. It might work if you insert an AT&T SIM card that is active. It can get notifications from the AT&T network that there is an update. Are you on 4.1.1?
I'm on 4.1.1 and I managed to update it with foreign sim card on one HTC ONE X, however I'm trying to the same with one more phone and so far only shows that I'm on 'latest' software and no need to upgrade. Tonight I tried again, and it says "SERVER UNAVAILABLE", I'll try after midnight, maybe I'll make it again. But, I did update without AT&T card on freshly SIM unlocked phone once.
First I downloaded and installed some small update and after that I did have to reset phone to factory default since software didn't allowed 2nd upgrade, I have to wait 48 hrs according to them to try again. However, I did reset it to factory, and after proper log in I was able to download some huge 600MB update or something, and it was 4.2 update.