The description sound more like a hardware than a software problem. Post a wiring diagram. I guess either the flyback diode on the relay is missing or the power supply isn't robust enough to feed both, the Arduino and the relay.
The description sound more like a hardware than a software problem. Post a wiring diagram. I guess either the flyback diode on the relay is missing or the power supply isn't robust enough to feed both, the Arduino and the relay.