If you are using a Pickit2, try enabling the 'Use Vpp first program entry' option under tools; I suspect that should solve the problem, from the symptoms you describe.