Multiple external power sources and one Arduino
Besides connecting all the grounds, a &quot;good idea&quot; whenever working with solenoids or magnetic (as opposed to solid state) relays is to add protection against inductive kickback, which can create really high voltages (hundreds of volts) when the current through an inductor changes suddenly. (The voltage is the product of the inductance and the rate-of-change of the current.)  The protection is simple:  Put a rectifier diode across each coil, with the arrow pointing to positive (reverse-biased).  The rectifier has to handle a big spike of current as well as the high voltage, so use something like 1N4004.
This protection will reduce the likelihood of spikes causing mysterious state changes in your circuits.