First thought is overheating especially as it won't restart right away. This could be a sign that the system needs to cool down before restarting. Suggest you initially check all the fans are working in case one has failed and post back.
I'm wondering as you mentioned about the fan hanging, if this could drag enough power from the power supply unit to trip the PC off. I'm not sure if it could cause enough of a drag to do this. Perhaps someone else could comment. Regardless of this, for the price of a fan I would just replace it as they are not expensive.