Just a thought. Are you sure the custom recovery you are trying to install is LOKI'd?. You can try to install OUDHS CWM via terminal commands.
I'm not sure if this has anything to do with your issue or not, but I read that people were having issues with certain versions of PhilZ CWM and the LOKI feature. They claim part of the issue involves corrupt backups that will not re-flash properly.
SGH-I337 (AT&T) 32GB
P-ROM (1st Gen.), De-Odexed, AMDL
Auto-LOKI OUDHS CWM
Make sure you read and understand the "PINNED" threads in the "General" and "Q & A" sections of the AT&T S4 forum BEFORE you ask for help. Use the forum's "search" function to find posts with additional information. You should not expect others to help you if you haven't tried to help yourself first. Also, read, understand, and follow the "XDA" rules.