To make PICKit 3 to work and solve this problem, first allow MPLAB IDE to update firmware before you can use it for programming.
Additional to MPLAB you can try to program from standalone application 3.0 :
PICkit 3 GUI and Scripting Tool v3.00 BETA
**broken link removed**
As you notice its still beta version.
Dont forget to update firmware!!!.
I have to admit that I'm not sure what Microchip wanted to do with the PICkit 3 programmer, works worse than PICkit 2. It is possible that they wanted to increase the sale of devices, because it would be harder to clone by home hobbyst. And in all this they started to play a little more, and we get product result. Of course they are a serious company and this will be solved.