Capacitor does not hold charge when switching power
The cause of the problem could be the relay's switching characteristics.

The 'pull-in' voltage of a relay would be closer to its nominal voltage whereas its 'drop-out' voltage would be much lower.

After occurrence of a power failure, the relay's 'drop-out' characteristic would ensure that it stays on in spite of the decaying power supply voltage.

Hence the capacitor would also get discharged before switch-over to the battery could occur. 

Here's an alternative scheme using a Schottky diode for switching.



The PSU would predominate, with it's voltage set marginally higher. In any case the probability of the PSU voltage exceeding that of the battery is quite high.

With availability of Schottky diodes having a forward voltage as low as 150mV, voltage drop during backup should not be an issue.