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)
That circuit doesn't connect to the AREF pin so can't have the required decoupling capacitor on AREF that's needed for low-noise ADC performance... All Arduino boars do this to my knowledge.
And what's the crystal for that appears on the left of the circuit. Your LCD display will use multiplexing to encode the characters which itself will generate lots of noise. You therefore need to ensure its supply is decoupled as close as possible to the display power connects.I know it's difficult to keep wires separated but all those wires crossing over each other will also cross-couple any noise signals to where they aren't wanted - particularly the one from the crystal (if it's an active part of your circuit)
Time for an accurate circuit diagram of the components you actually have wired into the system. Sounds like you've missed out the required capacitors on the voltage regulators. See vendor data sheets for subject regulators, where the manufacturers specify what capacitance is required at regulator input and output to prevent oscillation.