Faça um debug mandando a tensão lida do LM35 para a serial, parece que está havendo um problema com a referência ao terra, ou provavelmente, você está drenando muita corrente e a tensão está "caindo"
Está alimentando pela USB apenas?
Coloca uma fonte de 7-12V no arduino, pode ser que resolva.