With the following setup (and others like it, including gluing a Redstone Block to the side of the Fan) the Fan will sometimes not restart after being rotated to a new position.

This seems to be based on the orientation it got rotated from, as whenever I rotated the setup above with the Redstone starting on the West side of the Fan, the Fan failed to spin after the contraption was stopped.
It also seems to be partly based on what is powering it, as I can't get it to spin after rotating when it has a Redstone Block glued directly to the side of the Fan. However, it seems that the Redstone Block is still powering the Fan, as no amount of extra redstone signals will fix it, while removing and replacing the Redstone Block will (until it gets rotated again).

The full requirements for whether or not it will work seems to be based on some collection of data from the surrounding blocks, as the above setup works flawlessly if I place an (off) lever on the opposite side of the Fan.

I have had this problem too, and I made a separate issue before about links not updating or being updated or whatever when placed back down after moving sometimes.
Ideally, it would be that each block checks what redstone signal it should have, and updates other stuff that relies on whether it has signal or not, and so on. Same with changes in rotational power.
My similar issue: #315

0.3.1 - Fixed Encased Fans not providing kinetic power after being moved by contraption