Brian, if fresh devices program ok, and you have a problem only with re-programming, try enabling Vpp-before-Vdd in your programming software. This is a common problem with these devices if you are using the internal oscillator, AND have disabled mclr.