Do you have a diode connected across each relay coil?
See flyback-diodes-and-why-you-need-them for more information.