Hi,
Can I suggest you get the controller out of the gap between those two magnetic field producing devices.
What are the specs on the two valve coils?
From all you have done, it probably isn't power supply problems, but the magnetic field of the two solenoids directly affecting the Nano?
Do some dressing to your wiring to keep power wires away from signal wires.
If you pull out the controller and position it 20cm away from the valves and relays what happens?
Have you got your gnds and 12V wires STAR connected to the 12V power supply?
That way no current for the solenoids shares current paths with the Nano.
What is your power supply?
Thanks. Tom... 
