I had the same problem, I didn't set the option on the programmer to HS (High speed.) I used the MELabs programmer, just go under options and make sure the oscillator is set for HS. After that everything worked great. I'm assuming that you do have the correct capacitors on the crystal.

Jerry.