I have a similar mobo (GA K8NS Ultra). I actually had something similar with the CPU fan not working.
It turned out to be a BIOS setting called SMARTFAN. SMARTFAN will turn off the CPU fan when it figures that the CPU wasnt so hot that it needed a fan running. If you disable SMARTFAN (it is enabled by default), then your CPU fan should be running all the time.
I hope that is your problem, because it is an extremely easy fix
I put the new fan on and let it run and it worked for over 24 hours perfectly. I wasn't sure what the bios setting for fan control was so I went and looked and it was enabled. I disabled it like you said and it all looked great. I went home and when I walked in the door she called and said the heat beeper was going off. I sped over there to find the thing at almost 100 C. It then shut off. I went in and enabled smart fan and it has been running now for 12 hours and NO phone call. That has been the problem all along I guess. I had gone through bios settings and disabled this when I was updating the other day not realizing this would happen. I am going to contact Gigabyte and let them know and ask why this would be.