Why did a 1k resistor at the MOSFET gate solve my problem?
What may be happening is that your 1k resistor in combination with the gate capacitance is forming a low pass filter. This would cause the fan to experience an oscillating voltage instead of pure pwm. Iirc pc fans have digital controllers that may not play nicely with pwm depending on the frequency. By providing a voltage that never goes to zero, you may be allowing the controller to function continuously instead of resetting over and over again.