Try this... erase the PIC (so it has no code - and if you're able at the same time preset XT OSC and EXTERNAL MCLR). Does it then still give you an error?

From what I remember six years ago, some micropower PICs coupled with some programmers gave problems. I recall I had a problem, but it was fixed when I reported it to the Vendor that supplied the programmer, and they came out with a new version of programming software. Even now, some PICs (even some batches from PICs that hitherto never gave problems) require to be ERASED before programming, so as default I set ERASE BEFORE PROGRAMMING on everything.

When you WRITE to your PIC (eg ERASE and PROGRAM) it is possible the programmer is trying to verify that your PIC is the one you selected, before it starts writing to the PIC (also because different devices also use different programming algorythms). If the PIC is off doing it's own thing (being powered by the programmer and running on INTOSC+INTMCLR) then it may not be giving the expected response to the programmer in the time slot alotted. In my programmer software I have the ability to DISABLE or ENABLE the "DEVICE ID CHECK". If you have that option on yours, DISABLE it. The chances are that READ operations (ie READ or VERIFY) don't check the device ID.