Yu da man!
I had similar prob when I wanted to unroot my S4 "reformat" and after successful I couldn't update via OTA.... so I did it the hard way with Odin and then was happy, stuck my phone in a drawer for almost a year and decided to put it to service...... same problem again!...
After reading this thread, I realized since a new update was not available I'm getting the error whereas I didn't get it before....
I simply took my existing sim card in my activated Note 4 and put it in the S4 and wallah!... it worked! OTA!
My Verizon account didn't change anything because I didn't actually activate, just only switched sims "so no activation charges".... after OTA done, simply switched it back to my Note4 and now I have a fully updated S4 I can give away!..
Thx!