lsteele, I notice that your relays are powered by 5 volts. Is the source of the 5 volt supply the same as the PIC? If so I would have a separate supply for the relay source and a separate supply for the PIC. From what I have seen in the past you are working with electromechanical devices that have magnetic coupling and when you are opering the contacts the field is being coupled to the 5 volt supply the micro it is being powered from. If this supply for the relay source was separate and the ground paths are correct I see no problem with the operation of the relays switching the mains.

Dave Purola,
N8NTA