Check the pull-down or up resistors on the multiplexer/datalatch connection.
Perhaps you don't have any or too week.
If a command written to an MPX comes through, but out-puts are tristated after or during, the latch could respond to ANY capacitive induction (Multimeter changes state). Also check the diodes on the relays. Anode at collector terminal and cathode to DC.
If you're using small relays (say <200mA) a 1N400x would do.