Can you post a diagram or describe how you have the LM35 connected? Your results are consistent with seeing a 3V reading from the LM35 but you should not be seeing such a high value.
My best guess is that you have it connected incorrectly. With the flat side facing you the pins should be: +5, output, Gnd
I also could not find the part of the datasheet that mentions the offset voltage. The diagrams and tables seem to show that the reading only goes down to 0 unless you provide a negative current of 50 microamps to the output. Then the voltage can go to -550 millivolts but the Arduino can't read negative voltages.
@john, ive just had a look at the datasheet and your right about the offset. I was working off altered code and didn't double check.
ive attached a picture showing how i have the lm35 setup with my Arduino. As far as i am aware its connected correctly?? I just dont understand the high voltage output?
Those look like the right connections so the only other possibility is the your chip is fried.
I recommend the Maxim (formerly Dallas Semiconductor) DS18B20 thermometer chip. You can hook as many as you want to a single pin and use the OneWire library to talk to them. They give direct binary temperature from -55 to +125 in 16ths of a degree.