Could you post your schematic?

switching high inductive loads is always a challenge.

Some things that may help:

- Check for Ground Loops
- reverse diodes accross all coils.
- RC filters across the relays contacts
- RC Filters at the PICs and Drivers I/O Pins
- Many large Ground Planes
- Relays as far as possible away from the PIC
- opto-isolators between MCU and drivers
- If switching AC, toggle the relays at zero crossing !

etc...