I think you're down to physical separation between those power / solenoid devices, and possible shielding of the cables that go to Arduino.
Solenoids are, by definition, large inductors and when they are disconnected there is energy that has to go somewhere. MOV / R/C suppression across the solenoid is the usual answer. Also, you might try switching the solenoid with an optically-isolated zero-crossing TRIAC type solid state relay (like these: http://goo.gl/RbCNb). But sometimes the inductance of the solenoid make the voltage a current not be in phase. These should work at the 24VAC level OK with most solenoids.
People have beat these problems in lots of automated machinery. The physical layout and shielding are often important.
Let us know how you're doing!
DISCLAIMER: Mentioned stuff from my own shop...