OK we can try to help you but you need to explain your problem in more details. I've read your post three times and I still am unclear what the issue is?
Can you make sure that...
1. Your (presumably) new fan is connected to CPU FAN socket on motherboard?
2. It is spinning?
3. What fan did you purchase? Was it just fan or whole cooler (ie, radiator + fan)
4. Could it be you have a custom PC where you need to plug-in PWM fan and not just 3 pin? (some servers have it like that). Even though that fan is spinning if PWM is not detected it will report as fan failure.