The problem you are facing looks like a cable connection problem to me. So, make sure the CPU fan is connected properly and there is continuous power supply to the unit. Also, make sure that all the components are connected well with the PSU. Specifically check if PSU to motherboard connection and motherboard to CPU fan connections is right.
I have listed things in order so that it would be easier for you to troubleshoot:
1. Firstly, check if all of the components and PSU cables are connected right. Mainly the PSU connections to the motherboard and the motherboard to CPU fan connections confirming the proper working of CPU fan.
2. Also, Check the program you use that monitors the CPU fan speeds at the varying temperatures and see if it is working/set right.
3. If still you cannot figure out the issue, then disconnect the CPU fan/heatsink from the CPU and confirm the availability of thermal paste. If it is not applied, then add some. If there is some applied, then remove it and apply new thermal paste. Reconnect it all and see if that fixes the issue.
Hope that solves the issue !!!