you are more than likely experiencing electromagnetic interference due to radiated magnetic field emissions or conducted susceptibility issues. What kind of current is flowing through the relays?
in a project i have built, i am using a 8 channel relay (not all 8 channels are actually used) and i list where i got it in the first post. i only use 115 VAC, and the entire system only draws around 3 amps. the system has had no issues once i got all of the software glitches fixed. 
the suggestions to use a different source to power the arduino should work, or you can get a "Curtis filter" http://www.curtisind.com/RFIFilters/. these filters will help to filter out any common-mode or differential mode noise that may be on the line. another option to try would be to try separating the relay board from the arduino board.
i do not think you should have to go through all of this as i am sure other people have not had as many issues switching the loads you desire, but it may help.