So the "extra" diode is really an LED then?
"The relay is powered by the 5V from Arduino."
The 5V relays require 72mA of current. You have no caps near the transistors or relays. That's a decent slug of current on the 5V line.
Try putting 10uF caps and 0.1uF caps from Vcc to Gnd near the relay pins 4.