What does the Curve Editor look like?
For constant speed you need to set the In-Out interpolation to Linear.
You should only need 2 keyframes for constant movement.
Post a screen grab of your Curve Editor, or better yet, zip the max file with just the animated material, and post it here.