Can't turn down an opportunity to help sexy ladies and sexy things come together...

Have you seen this page?:
http://www.arduino.cc/playground/Main/RotaryEncodersI don't have the experience with the Max/MSP side of things, but rotary encoders are pretty easy to wire up with the Arduino. That page from the Arduino playground explains them pretty well. There is a basic sketch on that page which will output the absolute numerical counter from the encoder to the serial port on the Arduino.
To convert this number to a rate of speed, you'll want to divide the change in counter by the change in time. However, if you're trying to sync up a movie to the speed of the encoder, this probably won't be fast enough for smooth playback. Personally, I'd consider changing the code to just output a single character per "click" -- 24 per revolution total -- and do the speed computations in Max/MSP. (Or, advance one frame per click...)
Also, I'm not sure if you're committed to the Arduino, but something like this could also work well:
http://forums.bit-tech.net/showthread.php?t=86820It would let you use a standard USB mouse to detect speed, which would be trivial to patch in.