I believe I have resolved this issue now. I don't understand why my replacement fan wasn't working, but I suspect some issue with the wiring or encoder itself. When I bought the same brand of fan for my Lenovo x201 (KFTYR brand), and when the system got hot enough for the fan to turn on, it would always turn on for 2 seconds, off 2 seconds, on 2 seconds, off 2 seconds, etc. Although it would cool the CPU sufficiently enough, it was very annoying to use the computer. I ultimately removed it, greased the original fan, and put it back into the x201. No issue.
I fixed the issue with the Lenovo T61 by putting the old fan unit back in, but I think I found the issue. After time, the wires soldered to the encoder board of the fan get loose. it looked like there was a strand of wire on one of the cables touching either the GND or the adjacent solder point. This would explain why when I blew compressed air into the fan, it would sometimes boot up without a fan error - the air moved the wire strand at just the right moment so that it wasn't shorting another contact.
My conclusion, best to avoid these Lenovo fans with the KFTYR branding. I tried to order a fan recently which looked to be from Lenovo brand in the photo, but the seller send a generic.