PIC18 MCU Relay Issue
When you go to the logic high state, does this correspond to the contacts opening?  If so, you might be drawing an arc because of the inductive load, which will generate broadband RF. You might be able to suppress this by putting a series RC snubber across the contacts. Is your solenoid driven by AC or DC?