So I have been lurking around this forum for a long time, and decided that I should contribute.
Anyhow, I was facing the exact same situation as the original post. I was unable to update my phone using OTA. I even tried using Kies, using Triangle away, unrooting, all did not manage to get OTA to work. While unrooting, I used Odin to push files to the phone. Then I thought to myself, oh, what if I used Odin to push the updates to the phone? I did that and successfully updated to UVALL4.
So you can try these steps:
Run the Samsung Toolkit
Choose your version
Choose #8 from the main menu (Download, Extract + Flash Stock Rom via Odin)
Follow the steps in #1. This will download the stock Roms.
Next choose #2 and follow the directions in there
The choose #4 and follow the directions.
The first rom that you should flash over is UVALK8 if you are still on UVALK1. Or you can flash over UVALL4 if you are already using UVALK8.
Then the second rom would be UVALL4 that you flash over, if you are upgraded from UVALJ1
When all is done, you have should have now updated to UVALL4.
Some notes:
My phone was originally on STOCK T889UVALJ1
I unrooted, and used Triangle away to reset the flash counter to 1. It would not go to zero. Since you are more of less forcing the phone to update, whether you need to unroot and use Triangle Away I dont know.
I didnt factory reset either.
I upgraded from UVALJ1 to UVALK8 then finally to UVALL4.
The immediate difference from from UVALJ1 to UVALK8 seems to be more bloatware..
I also didnt any differences from UVALK8 to UVALL
I dont believe the above method will work if you are using custom roms. Be warned.