Have you double checked all the power connections? It seems to me that if the fans aren't coming on, perhaps they aren't getting power?
Another thing to check are the capacitors on the motherboard. If any are domed or turned black, they are blown, and a blown capacitor could cause the fans to stop working. There was one brand of motherboard that was having regular problems with blown capacitors. I can't remember which brand.
Does everything else seem to be working properly, besides the fans?