I tried clicking 'software update'
http://1drv.ms/1fJ5B3h (short video showing steps I've done)
Navigate to the Home screen then tap All apps > Settings > About > Software Information and locate the Software version. If your Software number is less than 5.18.502.1, you should proceed with the upgrade.
I tried updating via 'HTC sync'
This phone belongs to my employer and I was advised agains breaking the warranty. So the recommended / official way of updating software is preferred.
I tried inserting another (not AT&T) SIM and it tells me that it is locked. Is that a case that software update doesn't work without the SIM?