Hi Russ,
I use the PICKit2 and sometimes encounter that same scenario. The PICKit2 doesn't have an erase button (working from memory here as I am not home) so they say to select the chip you are using and program blank without selecting a hex file, to erase. This usually fixes the PIC and it programs when I load the hex. Crazy though it seems, when I get one like that my old JDM Clone won't erase it either.