the way around it is not using PWM, or switch to a tach separate from the fans power, like a little reedswitch glued to the outside of the fan frame and a tiny magnet glued to one of the blades
most of your generic computer fans actually give two tachometer pulses per revolution, make sure you have a pull-up resistor on the tach line.
instead of pwm, look into variable voltage control, this way the fan is constantly receiving power, not just short pulses of power.
not sure how you do it directly with a MCU, i'm using some specialized chips from Maxim to do it