[T-Mobile Samsung Galaxy S 4] widto08:
I had a similar situation like you described on my Vibrant.

What I had to do to get things right you probably don't want to hear, but here goes.

The culprit in my case was a bad download on the files I used to root the phone on the onset. My phone worked and all but was never quite right and upgrading recoveries was impossible.

First thing to do is to check the MD5's on all the files that you've downloaded for your phone. <---This I do now religiously, no MD5's posted by the uploader/dev, no downloads for me, no exceptions... (No offense to the uploaders/dev's, just not getting burned again by not knowing if my download is good or not).

My guess is, like me, you'll find that you flashed your phone with corrupted files early on. If this turns out to be true, read on to the end before doing anything...

Get your phone back to Original Stock as best you can. This includes resetting the counters in download mode using the available tools found here on XDA (my guess is this will not be easy with all this Knox crap we have to deal with now, pre-Knox = good. Another reason for me not to get Knox'd up lol).

Once you've done the above, Odin back to the original stock .tar.md5 firmware twice. Skip all the set-up/sign in steps between Odin flashes.

Now here's the important part

, after your first Odin flash let the phone boot up to the lock screen then shut down the phone completely and pull the battery and the USB cable, wait a minimum of 1 minute for any residual charge left in the phone to bleed out before going back into download mode (this residual charge seemed to cause some kind of "hook" on the files related to the recovery which, in turn, would not allow me to change them). Getting back into Download Mode, in this case, is done by plugging the USB cable in first then holding the volume down button and finally popping the battery back in. Do not let go of the volume down button until Download Mode shows on the screen, then proceed to Odin flash a second time. After all that is done you can re-root/flash a known good recovery/update flash to whatever ROM you wish and all should be GTG with your phone including recovery.

I spent a ton of time trying to get my phone working right back then (nearly a month IIRC) and only after doing the shutdown/battery pull/wait/boot into Download Mode using the steps described above, and Odin flashing a second time, did it work.

Interestingly enough I found that simply "rebooting" Sammy phones into Download Mode causes Odin to not flash correctly/not stick (most likely due to the residual charge not having enough time to bleed out properly. You can see this happen in real time by selecting "Restart" in the Shutdown menu. You'll notice that the led does not turn off until well into the boot process). This may be why so many people are having a hard time Odin flashing Modems or having to Odin flash them twice. At a minimum I would suggest, as others have in this thread, to shut the phone down completely, then use volume down/power button combo to get into Download Mode to Odin flash anything. I don't ever have a problem Odin flashing anything using this method and definitely never have to Odin flash anything twice to get the flash to stick... YMMV...

Hope this helps someone lol...