There are several problems here.
Turning on the solenoids causes a significant short term drop on the supply voltage. The actual voltage level doesn't seem to be a problem, but the rapid dip is. The obvious fix is to make less of a dip with slower edges. Put a bulk capacitor accross the power input right where it enters the board, and put smaller caps near the relays right where they draw power. Pay attention to the loop current thru these caps, and the overall relay power currents accross the board. The problem you may really be having is ground bounce when the relays kick in due to bad ground design. It would be best of the relay return currents did not run across the main ground plane, but had a separate return to the main ground point at the power supply feed.
Problem two is that your low voltage supply is susceptible to fast transients on the input. Since you have lots of voltage headroom, a little filtering in front of the 7805s will slow down the edges to where the active circuitry in the 7805 can deal with then, and also take some of the heat load.
Problem three is that the linear regulators are getting too hot. This is because they are dropping the difference from the power supply voltage to the 5 V logic supply times its current as heat. For example, let's say you need 100 mA at 5V. With 14 V input, the regulators are dropping 9 V, which times the current comes out to 900 mW. That's likely out of spec for a small surface mount part.
Adding larger regulators with heat sinks will be bulky and expensive. A better answer is to use a small buck regulator. Even if it is only 85% efficient (pretty low by today's standards), the same 100 mA at 5 V out will cause less than 100 mW dissipation. It can be small SMD parts without any special thermal considerations. One switcher should be good enough for all your 5 V needs.
If you need extra clean 5 V supplies, you can have the switcher make 5.6 V or so and use small low-dropout linear regulators at the point of usage. These won't get hot since they would only be dropping the 600 mV times the 5 V current. Put a small ferrite chip inductor followed by cap to ground in front of each LDO.
Another thing to do is to put a Schottky diode followed by a cap to ground in front of the switching regulator. This will prevent sudden drops in the input power voltage from forcing the input of the switcher low. The resulting transient will be slow enough to give the switcher a chance to deal with it properly.
Typically you would not like to switch big loads using mechanical switches, as they bring several problems. In particular, contact wearout due to inrush currents. This problem is exacerbated in presence of capacitive loads. When you turn-on a capacitive load, you'll get a large inrush current. Rugged contacts are needed to handle that current. This would be the case in which the capacitor is after the switch.
This is also the case the pdf you linked suggests. In fact, they want you to put that capacitor in parallel to the strip, so that the voltage at the strip will not increase abruptly when you connect that strip to the PSU (i.e. when you turn on the switch). With that big capacitor, the voltage at the strip will rise with a time constant, which is C * R, where C is 1000uF, and R is the wiring resistance + contact resistance + PSU output resistance (* see note).
If you don't put such large capacitor, the voltage at the strip could rise "instantaneously". This would create an inrush current on the strip, which could be very high. In fact, for each LED (see pdf) a 100nF decoupling capacitor is mounted. Since the LED density might be as high as 144 LEDs/meter, you would have 14.4uF per meter. Say you have 1 meter, so 14.4uF. If the voltage rises with a 14.4us time constant (this automatically implies a total parasitic resistance of about 1 Ohm. I guess this is too much), you'll have a spike with an initial inrush current (I=C * dV/dt) of Vdd*C/Tau = 5 * 14.4uF/14.4us = 5A. This is an additional current, which must be added to your load current, and could damage something (the strip traces).
If you put that additional 1000uF capacitor, the voltage will rise with a much slower rate (dv/dt). There will be also a much larger current spike, but not in the LED stripe, but between the PSU and the capacitor.
However, if you put that big capacitor AFTER the switch, the inrush current could damage over time:
1) the power supply;
2) the capacitor;
3) the switch (as a large spark will occur when contacts close).
If you want, consider using a pMOSFET/integrated Load Switch, where you can easily select the turn-on/turn-off times, then drive it with a smaller/cheaper switch. In that way, you can limit the inrush current. Just as an example, look at the application circuit of Si1865 http://www.vishay.com/docs/71297/si1865dl.pdf. Of course you must choose a load switch or mosfet that can handle that current (therefore the SI1865 won't suit your needs).
Leaving that big capacitor as it is now, it's even much more deleterious than not having it at all, because you're even reducing the PSU output impedance.
Notes:
* you must include the PSU output resistance when its output capacitor is much smaller than 1000uF.
Best Answer
One of the purposes of C1 is to help damp-out input voltage overshoot. The 50 to 100m cable has a lot of series inductance. If you were to put, for example, a 10uF ceramic cap in place of C1 you will probably have a very large voltage overshoot when you first connect the regulator. Very possible to blow up the regulator first time you plug it in.
I do not know if 1000uF is needed. But if you make any changes, make sure you test for overshoot. Electrolytic caps generally don't overshoot as much as ceramic because their effective series resistance provides damping. It is also possible to add a resistor in series with a ceramic cap to get the same effect (but you may have trouble finding a 1000uF ceramic cap!). Also, if you add a fuse or PTC to the circuit, that may provide some damping. The amount of resistance needed for damping may less than an Ohm. Simulation can be done if you have very accurate models. Otherwise you can test it and monitor the overshoot with an oscilloscope.
Application Note 88 by Goran Perica of Linear Technology goes into a lot of detail about input voltage overshoot.