Prevent full startup when only battery backup applied
You could arrange it to only apply the initial 3V battery connection when the unit is already powered at 5V. 

Another approach would be to add a flip-flop or latch circuit that is powered by the 3V and initially comes up in a state to hold the MCU in reset until the 5V has been applied at least once. Applying the 5V would set the FF/latch to the opposite state where it would stay until the battery was changed. 

If it turned out that holding the MCU in reset didn't prevent the "freeze up" that you are experiencing then you would design in the same type of FF / latch circuit but instead have its output drive the gate of a small P-Channel MOSFET that would be used to gate power to the MCU. This would keep the MCU truly OFF until the 5V was applied for the first time after a battery change.