Hi,
Can I suggest you rebuilt the LM35 circuit on the other side of the centre of the board, not on the side of the fan 12V bus.
I can't see it directly, but is the transistor that switches the fan on the side of centre where the 12V fan wiring is?
Also some 0.1uF capacitors on the board, one on the 12V BUS and another on the 5V side.
Another across the Vcc and gnd pins AT the LM35 might help.
Tom.... 
