You can this message when you try to erase the PIC using the ICSP method too. Did you place your PIC directly in the PicStart ZIFF socket?

Sometimes, Picstart could be a nightmare... Try to add a 0.1uF Between VDD and VSS directly on your ZIFF socket and retry... about now?

Do you have the Latest PicStart firmware install?

Sometimes, they provide some workaround the the Help file too for some devices.