the problem is your PIC programmer. I would bet on a JDM type. This message appear often on those because of few things

1. too low Vpp/MCLR voltage during programming
2. poor timing

things are getting worst if you have a USB-2-Serial converter.

If at all possible, consider to purchase a real PIC programmer such as Melabs EPIC or Microchip PICKit2. PICKit 2 ~35 USD$ and USB. Works a treat.

How do you program your PIC right now? in a ZIFF socket or In-Circuit?