Replacing BD139 for TIP122 - Cooler speed control circuit
Sounds like there is something wrong with the fan. According to the datasheet, the fan should start with 4.5V across it.
See if the fan blades spin freely or if there is some binding. Maybe there is something in the operating environment that is affecting the fan.
In linear operation, worst-case power dissipation of the transistor is around 0.75W, so about 100’C rise above ambient for a TO-126 sans heat sink, which is pretty hot. You also have marginal base drive to get it to saturate- maybe review how you calculated that 1K was adequate.
The TIP122 is a Darlington pair so it has higher voltage drop than a BJT when fully turned on, perhaps 750mV with 1mA base drive and &lt;250mA collector current.
Anyway, my main point is that the fan should be spinning with &gt;4.5V. Secondary points are that the BJT has marginal or inadequate base drive, both transistors should have a small heat sink, and both transistors appear to be behaving within the range of expectations.
If you just want to turn the fan on and off (or drive it on/off with PWM) replace the R,C,and transistor with a small n-channel logic-level MOSFET such as AO3400, which will drop less than 10mV when on.