Sounds like the fan speed might not be up to par. Something like a dragging bearing might be slowing it down. I'd replace it with new.
BTW ... where do you see this FAN error as for only servers that have FAN Fault indicators will keep running with a fan that is not up to par. On most systems a fan failure is indicated by the system shutting itself off unexpectedly or after so many seconds of initial power on in which the tach signal isnt detected and it protects itself by a hard shutdown.
A slow moving CPU fan might be just fast enough to keep the watchdog circuit satisfied that a fan is present and working to keep a system running without a hard shutdown, ... but fall behind in cooling due to lack of airflow from slow moving fan.
