It sounds to me like the PIC itself is not bypassed properly. Make certain that you have several .1uF caps very close to the chip across the supplies. Also make sure that you have some bulk capacitance ( > 100uF) close to the chip. You may need several.

Two other things to watch for: The crystal needs to be very close to the PIC.
The MCLR line needs to be short, and pulled to VCC with a 4.7K (or so) resistor.

At least in my experience, some chips are more prone to noise problems than others. I have had issues with 18F452's but none with 18F8720's (in basically the same circuit) for example.