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.
John
John