Urgent help needed - relay with load resetting Arduino

After spending the past six hours debugging, I think I may have narrowed down the culprit. I don't have 0.1uF cap in hand, so I used 0.33uF cap across Vcc and GND at pin 4 of the relay. The problem still persists. Then I stripped down my code, removed the Ethernet shield, and just have a command-line turning on/off a specific relay. That's when I found out that the culprit may be the shift register matrix I am using to control the relays. Attached is the schematic of the shift register matrix, which consists of two shift registers for the 16-bit row and two shift registers for the 16-bit column. If I connect the solenoid to the relay, all 16 row LED's on the shift register matrix are turned on after the relay is turned off. So I added 0.33uF across the Vcc and GND on all four shift register IC's, and added a pull-down resistor on the latch pin of all four shift registers. Now instead of all 16 row LED's turning on when the relay is turned off, the serial port receiving stops working (I can still type to turn on/off the relay). So it is more stable now, but still some interference.

Any suggestion on what to try next? Thanks.

shiftRegister.pdf (54 KB)