Could be a couterfeit LM35 if you have them from an ebay seller.
Try a 100n decoupling capacitor on the VCC/GND pins on the sensor (close to the sensor).
If that doesn't work, throw them away, and buy the digital DS18B20.
If it works, use this sketch, with a 5x higher resolution.
Leo..
// connect LM35 to 5volt A0 and ground
// calibrate temp by changing the last digit(s) of "0.1039"
float tempC; // Celcius
void setup() {
analogReference(INTERNAL1V1); // Mega's internal 1.1volt Aref
Serial.begin(9600);
}
void loop() {
tempC = analogRead(A0) * 0.1039;
Serial.print("Temperature is ");
Serial.print(tempC, 1); // one decimal place
Serial.println(" Celcius");
delay(1000); // use a non-blocking delay when combined with other code
}