If you have tried dropping the PK3 voltage a little, and it still doesn't work, then I would try powering your board from an external supply. If that works, at least you will have identified the problem as the supply in the PK3. I would then give Microchip a call. As many have mentioned here, including my own personal experience, Microchip is quite generous with replacing PK3's. In my case, I opted for an ICD3 at an attractive price.
I am assuming your target runs on 5 V nominal. In that case, do not turn on the lvp. Just lower to target voltage to 4.75 or 4.8x. Your chips should all work fine.