Arduino Uno: external power supply +5V and serial communication with pc over USB
I have a similar rig using a 4-channel optically isolated relay, but I use different power supplies for the Arduino and for the relay. (It works perfectly.) My guess is that the relays are causing the voltage on your arduino to droop when they switch on. I suggest using separate power supplies.

As @Majenko suggests, you might try adding a filtering cap (capacitor) between +5V and ground very near the Arduino. The cap should slow the drop in voltage to the Arduino long enough for the power supply to recover, but separate power supplies is the surest fix.