Another point to check just came into my mind:
The PIC you are using has internal PLL - did you check its configuration?