Interrupts problems due to noise

Unlikely. We need your schematic.
Do you:
Have lots of bypassing?
Seperated the power for the arduino and the relays?
Put diodes on the relays?
Tried opto-isolating the relays?