From the symptoms described, I would be looking (with a scope) at the power supply. If the 5V relay draws slightly more current than the power supply can sustain then I would expect BrownOut Resets some short time after the relay energises.

Just a thought.

Brian