Make sure the ISR that's "calculating" the rpm isn't doing anything else (but storing the last rpm value or it's reciprocal). Then in your main loop, say once a second, take the rpm value(s) and send it where to need to (LCD, RS-232).

In my SmartKart project I was able to do 20k no problem (sorry it was HC11), but the jist is that you need to keep the *measuring* of the RPM separate from the *reporting* of the RPM.

'Hope this helps.

GB