I would pay close attention to the transients generated by the relay coils when switching. I like to use hexfets because of their high gate isolation from the drain and source. You have to add a reverse biased flyback diode like a 1N4001 accross the relay coil and provide further isolation from your port pin to the fet's gate with a resistor, perhaps 4.7K. If you have pic port wires in close proximity to the relay source/sink wires, you can get induced noise in the pic causing havoc as well.