Look closely at the gnd wiring of your project. Get the gnd connection of the Fan as close as possible to the gnd of the UNO.
It sounds like your LM35 is sharing a considerable length of gnd circuit wiring with the fan.
Tom....
