I'm attempting to update my SGS III (purchased from 2 Degrees) to the latest firmware version OTA, but I've tried three times now, and each time it's failed and told to me to either use Kies or take it to Samsung support.

Unfortunately, I've tried connecting to Kies, and it thinks I've got the latest firmware version already (PDA:LE8, PHONE:LE8, CSC:LE5 (NZC)). Build number on the phone is: IMM76D.I9300XXALE8, with baseband of I9300XXLE8. The firmware is stock, but rooted via a method I found elsewhere on Geekzone (using Odin) - that could very well have something to do with it.

Any suggestions as to what's going wrong, and how to fix?