what type of programmer do you have? I had an offbrand pickit2 that when it started to become faulty, it'd cause the same symptoms that your experiencing, the chips were fine, but the programmer was fine.
I know some jdm programmers, if there isnt enough power on the serial port, it will cause issues like that too.