Handling power loss in a Microcontroller
You are reducing the voltage available for the semi-LDO LM1117 before you even get started, so the hold-up time will be reduced significantly. You could use a better regulator and gain that back (and then some), but parts cost will be increased.

Also, particularly at high temperatures (which you may not have yet tested for) Schottky diodes are leaky. There is a trade-off between forward voltage drop and leakage current. 

Perhaps you should also check the diode It's possible the startup surge from charging the 1000uF has caused it to go shorted. You don't have any current limiting at all in the circuit, and if you apply a stiff 5V source the diode will see a pretty high surge current. And as @oldfart quite reasonably comments, if there are other hidden parts to the circuit such as a 5V capacitor that you are not showing, there is no way we will be able to figure out what is going on. Please consider my final paragraph though, which applies in any case. 

Umm.. why don't you just turn the relay off via the microcontroller, before the 'save' operation commences? You may want to add a pull-down resistor on the gate so if the GPIO goes high-Z the MOSFET is guaranteed to turn off.