DuaneB:
guys why wouldn't you use a counter ic as a prescaler on the 6000 pulses per second ?
Bingo. Bring that max 6000 pulses-per-second down to a more reasonable number by dividing by (e.g.) 2, 3, or 6. That relaxes the demand on the AVR handling interrupt requests considerably. High dividers trade reduced resolution for less processing time. Assuming you're just looking for a heads-up display for RPM, you don't need single-revolution precision anyway.
(Although, in retrospect, it looks like this is basically what Nick was suggesting by using the timer input to fire once every however-many pulses.)