LM35 readings are erratic
I've had a look round and spotted this:

https://electronics.stackexchange.com/questions/117970/why-is-my-analog-temp-sensors-signal-so-unstable

In summary it says that the fault maybe that the Arduino's 5V isn't stable enough, so you need to decouple it.  For once it seems that running from batteries may have been a better idea.

I've also seen posts saying there should be a 500Ohm resistor between the Ground of the LM35 and Ground.  Apparently it says 499Ohm on the datasheet.

And as a final resort I saw said that the 'Data Direction Register' influenced the analog pins.  If it was set to digital output this could lead to unstable readings for the ADC.  Basically it implied you needed to set the analog pin's to pinMode (A0, output). But I really don't think this will work