It sounds to me that you might have an extra keyframe in there somewhere. Or that the animation of the sun and the hue shift don't match, maybe? Linear should be ok as far as curves go.

I've tried the Mr Sun and Sky for Maya 8.5, but I didn't need to animate anything except the sun. Maybe don't animate the hue shift?

Hope this helps.