first thing to do is to use a multimeter to test the connector that the fan plugs into. if it proves to be bad then you will have to buy an adapter that lets you run a 3-pin fan from a standard 4 pin connection. these are cheap, as in <5 bux. also, you should check all of your voltages on your main wiring harness that connects to your mobo, because it sounds like your power supply may be dying, a voltage jump caused by this would be consistant with your fan failure. so if anything is off on your power supply, you better replace it before it spikes somewhere else, you'll likley fry somethin.
AMD 64 3800+
X-connect 500W psu
Custom Quake box under planning and soon to be under construction