Learning how my circuit works (PWM a 5V USB fan)
I'm thinking that for some reason PWM was faster than your transistor (which means it would behave the same with a FET)... So as you suggest in #2...
From your schematic, there is reason to believe that the capacitor and the LED are just holding the voltage at (VCC - VLED), which just turns on the transistor at the maximum current allowed by your resistor. If you want to be able to control it via PWM, use an RC filter to smoothen out the voltage. In simpler terms, switch the places of the resistor and the LED.
Yes, the diode has been placed correctly to prevent inductive kickback (at least, to the battery), however for full inductive flyback protection, you should move the diode to being across the fan.


Here's an image of what it should look like once you've made all of the changes:



But otherwise, good work! :)