Hi Jamie,
There should be no problem with the CCP hardware, it can run up to a few hundred KHz. Your code looks OK too. Have you put 'scope on the output of the LM1815? I'd suspect this first. You could also try connecting a signal generator to the PIC in place of the engine/sensor/LM1815/ combination.
It is possible that you are getting interference from the engine at higher speeds that is not connected to your RPM signal.
You don't say how you have configured the LM1815, this could also be the problem.
Get your circuit running on the bench with a signal generator (another PIC will do the job) first. It's safer than by the engine, and you can hear yourself think!

Robert G8RPI.