What OSC are you running the PIC at?

Look at the electrical specifications in the PICs data sheet to see what speeds work with different voltages.