Rotation at odd angle -
Whilst I concur with the comments above, I remember doing this at some previous time.

The cube, shaft and 'propeller' here were added at the default location 0,0,0 and at the default straight x,y,z angle. I'm not sure this matters.
The shaft and 'prop' were parented to the cube.

To experiment, the cube was then rotated at around 45 degrees in all 3 axis'.
-=============-
WARNING - Do not use CTL-A (apply) on any of the 3 components.
And for info - Keyframing as mentioned below was always done by hovering the mouse in the locatio/rotation slots at right and pressing "i" .
-==============-
The "Orientation" menu at bottom of window was then switched to "Normal".
Fearing a manual entry in the prop's X axis would be applied globally, after keyframing a zero in it's X rotation slot at frame 1, I advanced the timeline cursor to frame 80 and rotated the prop several times with the keys RXX. This was the (normals) axis that aligned with the shaft. The mouse was used to drag the actual rotate. That was then keyframed and it worked fine.
I'm not sure if this rotation experiment was necessary but it did provide reassurance.
A more adventurous rotation was then manually entered into the prop's X rotation slot at right: -36000 at frame 80. (100 rotations over 80 frames)
When run the animation rotated correctly.
The cube's location and attitude were then changed and keyframed and everything still remained stable. An animation speed of 120 fps was used to check this.
-==============-
To conclude and whilst not recommended, when necessary however it appears you can get away with perpendicular rotation at odd angles, in Vers 2.77a at least.
The Blend file is available on request but the key to it's success is probably due more to the order and manner components are added, rotated, and keyframed.
There were no active modifiers or constraints used apart from parenting.
It shouldn't make any difference but the above was rendered with OpenGL.
Further, when CTL-A was used, everything went haywire.