Here's a weird one for y'all.
Little background: my front intake fan has been broken for a while now, I've recently purchased a new fan to replace it, but I've also recently bought a new video card as well.
So I crack open my case to install the new card, everything goes fine. I don't get around to the fan because I don't feel like doing it right then. Anyhow, I boot up with my new video card (the resolution defaults to 800x600) and voila! my front case fan starts spinning for the first time in months. Needless to say, I'm confused. I go on and install new drivers for my video card and reboot. Lo and behold, fan doesn't work anymore (just like it had before I begun). I have no idea if this has anything to do with software, it could very well be just an eery coincidence, but I wanted to see if anyone had any clue. My best guess is some faulty power or something.
Sounds like an intermittent short. What is the power connection to your fan? a standard molex? If so then try a different one. It would also just be a weak connection that a different connecter may fix