Toght the too low supply is the problem. Powering a PIC at a lower voltage and at max clock is like running it overclocked on its rated supply voltage.
If you look in the DC characteristics part of the datasheet there is a graph i think that shows supply voltage VS max CPU clock. It can be used to look up how fast can you safely run it at a certain supply voltage