Just a shot in the dark; when I design a power supply for my PICs, I isolate the 5v (or 3.3 or whatever) regulator with a 10 ohm resistor from 12v (or whatever) and place a 10 uF and 0.1 uF cap on the regulator input side. Then I put a 100 uF and 0.1 uF (and sometimes a 0.01 uF) parallel caps on the output side (5v side) of the regulator. In addition, there will be some distance between the regulator and the PIC. The VCC pin(s) get(s) an additional 0.1 uF cap to help filter any spikes. These larger electrolytic power supply caps add reserve when a brief power drain occurs, and the small disc caps filter noise. Microchip has released numerous Application Notes regarding power supply filtering and the importance of it. Just for kicks & giggles, give additional power supply caps a try and see if anything changes.

[I have a large periodical table of elements I hang in my work area. I write often-used formulas there, as well as a resistor color band chart. I made a note to "Add more filter caps" and "Add more test points on PCBs" on my table because of issues I've had in the past.]