Michael, I noticed that the LCD display dimmed each time the relays closed, which indicated to me that the power supply was not completely adequate. Thus each time the relay closed, there was a voltage drop across the board and this could be causing the uC reset.
Effects of decoupling caps demonstrated: http://hackaday.com/2011/10/25/do-you-know-why-youre-supposed-to-use-decoupling-capacitors/
Two useful references I use WRT to decoupling are:
http://www.atmel.com/Images/Atmel-8580-TPM-Power-Supply-Decoupling-ApplicationNote.pdf and http://www.atmel.com/Images/Atmel-2521-AVR-Hardware-Design-Considerations_ApplicationNote_AVR042.pdf.
Note the info about the RESET switch.
Furthermore, I understand that the capacitors also serve to reduce the switching noise (voltage spikes) from the uC messing up the supply. This is critical in cases where you have other IC's using the same Vcc but doing analog work. While they are there primarily to keep the noise at bay, providing voltage support for the uC is a nice side benefit. Either way, use bypass caps.
Another interesting read is : http://web.archive.org/web/20060621061926/http://www.dvanhorn.org/Micros/All/Bypass.php and https://www.avrprogrammers.com/articles/basic-hardware explains a lot of my circuit design choices.
Sizes: Larger caps have larger inductance, many times that of the smaller value cap, so their inductance limits the frequency range that they will effectively filter, while smaller caps react to voltage spikes faster. So generally,
the best is a .1uf smd cap right at the supply pins as well as the 10uf electrolytic a bit further off.
" In theory any cap bypass cap has less and less capacitance reactance (AC resistance) to ground (which is good , acts like a high pass filter to ground) as the frequency of the noise or spike increases. However in practice different capacitor's dialectic material used for a specific kind of cap can have different ESR (equivalent series resistance) values at same frequencies. So larger electrolytic caps are favored for their effectiveness at lower frequencies (for say AC power ripple frequencies) while ceramic caps are better at higher frequencies. Also where the caps are placed can have a big effect on how well bypass filtering work. The larger caps work better by placement at where power enters the board or right at the output of a voltage regulators, where as the smaller popular .1ufd caps are usually more effective mounted right at the Vcc terminals of any ICs being protected. You will note that the arduino board design for a 328p chip has 3 .1ufd caps wired close to the chip at the Vcc, Avcc, and Aref pins, all used for bypass filtering. "