I'll come back to Grumpy_Mike's suggestion.
I've disconnected everything from the arduino except the LM35 and disconnected everything on my breadboard (see picture) from the +5 and gnd.
At ambient temp in my room I get values from 29 to 34 jumping around all the time (representing 14.21 degrees C to 16.66 degrees C) and also this seems a little low, I'd expect it was around 18/19 degrees C and this represents around 180mV (18 degrees C).
Interestingly if I put my fingers over the LM35 it rises to an adc value of 57 and is consistent then when I remove fingers it steadily drops (no jumping around by more than 1) back to 38 or so then the jumping around starts again.