Matt,
Have you tried posting this issue on the Cycling74 website?
There are more Max users there- and there is a special project just for using Max with the Arduino (Maxuino).
Chances are you'll get some good answers.
I've just started using Max myself- but haven't tried interfacing to the Arduino yet.