It sounds like a wiring or power supply issue to me. Post a photo of your setup and preferably a schematic too, then it will be easier for us to help.Back emf is generated when the solenoid is switched off rather than on, and can be tamed by connecting a diode in parallel with the solenoid, cathode to positive end, anode to negative end.
Try moving the Arduino further away from the solenoid and its wiring. In particular, that coil of red wire will create a varying magnetic field when the solenoid switches on or off, which will induce currents in anything close to it.Also connect a power diode in parallel with the solenoid (1N4001 will do), or a snubber network across the relay contacts.
If you are driving the eBay relay module from the Arduino's 5V supply or from the same supply that is powering the Arduino, then the optical isolation is doing nothing useful. It's only helpful if the relay board has an independent power supply.On your custom relay board, did you remember to include a diode across the relay coil?
also since that is a pretty big solenoid, throw a low ohm resistor behind your flywheel diode, this lets the resistor dump the power instead of the diode. google info on it, but I think a 1ohm or so would be a nice number. I dont remember, it was a wihle ago I needed to look up some stuff like that.