I think you have Maya set to use quaternion interpolation rather than euler rotation interpolation. You may have it set that way in the prefs. You can also change it at any time in the graph editor by selecting the rotation animation curves, going to "curves" in the editor's menu, and going into "change rotation interp" and setting it to euler.

Using quaternions is sort of like trying to use the theories of quantum mechanics to walk. It won't behave in the way you'd expect and the next thing you know your scaring children and old people alike on the street. But the euler interpolation method will jive with what you would expect to happen when you set an object to rotate a certain way or you move a rotation keyframe up or down in value.

I believe that should fix your problem. I hope.

http://www.petergreenstone.com