What is the mobo? I assume that you have the CPU fan connected to the mobo's CPU_Fan header? That's where the fan RPM is monitored, and power is provided.
Sometimes there's an RPM threshold that the fan must meet or a fan error will be declared by the BIOS. I think typically this is 1500 RPM. This may or may no be adjustable in your BIOS. Another possibility--does the CPU fan connector have three or four pins?
Finally, did you use the stock HSF that came with the CPU or use another? It may be possible that the HSF you used is a variable speed type and is running below the BIOS error threshold.
"Anyone who has never made a mistake has never tried anything new."