I wouldn't just assume that it "must" be talking about the case fan and not the cpu fan when you get the error message "cpu fan failure". Kind of risky.
It is a tricky problem you have, as it could be anything from faulty sensors, to corrupt software reading the sensors, fans connected to the wrong ports in the mobo, or actual faulty fans.
The thing is, if you DO have a faulty CPU fan, then this is quite dangerous to your system, and you'll want to fix it right away.
Boot up into your bios and take a look at the rpms of your fans. Or better yet, open up your case and take a look at the CPU fan itself. Is it spinning? Is it caked in dust?
Do you have your manual for your motherboard? If not, go to the maker's website and download it. Find out where the CPU fan is supposed to be connected to your motherboard. The connector is usually RIGHT beside the CPU/heatsink.
What about the fan you recently installed. Is it plugged into the motherboard or directly to the PSU? How many rpms is your new fan rated at, and in your bios what is it set to for the alarm? You may have purchased a really low rpm fan (quiet fan) and your motherboard thinks it is malfunctioning.
A lot of questions I know. Hard to diagnose when we can't get our eyes and hands on your system, but hopefully this is a good starting point to help troubleshoot.
Good luck!