Hi,
I had a simmilar problem with the 18F2431. With help from other forum contributors this was found in the PICStart help-file:
PICSTART Plus Limitations for PIC18F2331/2431
All power supply (Vdd and AVdd) and ground (Vss and AVss) pins must be used in order for these devices to program. PICSTART Plus will handle Vdd, Vss and AVss properly, but you must place a 1kOhm resistor between Pin 7 (AVdd) and Pin 11 in the socket with the device for proper operation. There are other devices that may require the use of all power supply and ground pins. Consult the datasheet if an unexplained programming problem occurs, such as inconsistent programming.
May be something to look into.

/Henrik Olsson.