In my opinion there are two possible issues:
First, when the +5V is not stable your ADC reading will vary because in standard mode +5V is taken as the reference voltage for the ADC. You could try to take the internal 1.1V reference for the ADC.
Secondly, the LM35 can have a swing problem, especially when your wires are long (1m can be enough). I had this once, too. This is hard to track because it appears only sometimes (due to noise in the system). I wrote a post in my blog
about this point. If interested, look at:http://heliosoph.mit-links.info/connecting-an-arduino-with-a-lm35-temperature-sensor-special-issues/