You might also want to ground pins 7 thru 10. They should have no effect in 4-bit mode, but it's best to remove them from the equation anyway.
When I last saw the code for "A" it was pure polling, so it shouldn't be an interrupt screwing with the communication.
One other thing to check is the flyback diodes on the relays. Without those, as the relays switch on/off (especially off) it could induce massive spikes into the power system, which is far more likely to cause problems than mains noise. A small ceramic capacitor can also help with that.
It's hard to see how you're driving the relays on those pictures. Do you have transistors driving them hidden away somewhere? I can just about see the flyback diodes on the underside - are they the right way round? I can't tell 