Using Internal Clock of Arduino Duemilanove

OK, that sounds sensible.
I just had to ask - you be amazed at the number of people who overspecify because they equate "RPM" to "Hz".
I'm not sure why the encoder needs to be synced to the processor clock though. Need to have another read of the datasheet.