Please don't give up on your phone yet. It isn't that bad yet. The dreaded error message you are getting means that your recovery system is compromised. Also, once rooted, your phone stays that until specifically unrooted. Even a factory reset will not remove SuperSU and Mobile Odin and the definitive solution to un-rooting is to flash a complete stock image. However, you may be able to fix the recovery issue and get updates in a number of ways. First, you could reflash a complete stock 4.1.1 image via Odin. This will update all system partitions including recovery and should deliver a new and working recovery partition. It will also remove root and make it possible to get an OTA update to 4.3JB. You can download the Odin flashable file from Sammobile.com or from the following link ... http://www.4shared.com/get/zAmWJ54J/...TDLK3_ATT.html
Unzip and extract the *.tar file and flash via Odin.
The second solution would be to use Mobile Odin or Desktop Odin v3.09 to flash a new recovery partition. You'll need the same *.tar file for UCDLK3 but you'd only need to load the recovery partition. If this is successful, you can try the manual update process again.
The final solution would be to flash custom recovery via Odin and then flash the 4.3JB stock restore image via (custom) recovery. You could do the same 2-step manual update via custom recovery. However, a complete stock restore image is available for 4.3 which can be flashed via custom recovery. Please see the first page of the thread below ...
You can find the TWRP custom recovery Odin flashable file for your device via the link below ...
Hope this finally solves it.