1) a ground loop
2) noise
3) insufficient decoupling

for 1) and 2) install opto-isolators between the uC and the relays. Ferrite beads across the drive wires where they leave the box with your uC would be nice. DO NOT connect relay ground to uC ground, you may need to use 2 power supplies to achieve this but DO NOT CONNECT.

for 3) make sure you have 10-100 nF capacitors across every chip and make sure you have a reversed diose across every relay coil.