I thought trying a new 4431 here might shed some answers ... but I don't think this will help a bit.

I've programmed it here with both the U2 and PICkit2 programmers.
It works everytime no matter what I try.

Unfortunately, I only have one 4431 in my bin.

The Device ID/REV in my chip is 0882. Is yours the same?
(meProg | Program | Get Target Information)

If I could be sure that the U2 programmer works with no problems I'd buy it, or the PICKIT 2
I like the PICkit2 better, but I have several programming adapters and ICSP cables wired for meLabs 10-pin format. So I usually end up using the U2. The PICkit2 has a 6-pin connector and I'm too lazy to make new cables.