Something on your veroboard is creating serious noise. may I suggest you provide both a circuit diagram and photos of both sides of your board. Also, do you have any active circuits on the board (such as amplifiers or oscillators etc)
I am attaching the pics here..

The circuit is pretty simple..
I have a 16x2 LCD attached to PINS 12, 11, 5, 4, 10, 9
a voltage divider with R1 = 2.2k & R2 = 820R is connected to A0 to measure voltage.
A LM7805 as a voltage regulator for the circuit.
2 nos. tactile buttons attached to A5 & A4.
Thats all what I have...
I tried with opening the 1mtr wire from the A1 ( pin for LM35) and connected the LM35 to the A2 with a Short wire, the noise persists. So I tried connecting the LM35 to A3 still the problem persist.
I even detached all the other connections from the Analog pins.. Still the problem persists...

So I pulled up an Arduino Duemilanove board and connected the LM35 to It and checked.. There was no noise...
So the LM35 is good..
What may be causing the noise...