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.