http://www.arduino.cc/playground/Main/ReadingRPM
Fans run at 3000rpms and this seems to work fine.
I'm not sure how the fans get the hall effect sensor to output +5v pulses so you may want to look at an hall effect sensor that has the circuitry to do that for you.