Do you have the code protection bit set in your configuration bits? If you do, and the programming software writes the configuration bits before flashing the program, it won't be able to read back the memory to verify it.
Try doing an erase of the PIC and then turn off the code protect bits in the configuration word and see if that helps.
I know when I use my PICKit 2 it writes the program first, then verifies, and only after that it writes the configuration word, so the protection isn't set until after verification.