OK 220R is very hefty so it looks like you need to reduce the emissions rather than any protection on the Arduino.
Try snubbers on the power lines. Basically you need to slow down the rise time of the current into the coils. Have you got diodes across the relay coils?