I have managed to resolve my problem.
Whilst there was some considerable noise generated by the PSUs, it wasn't the real culprit.
I'm glad you solved your problem!
In the end I added some code I found using google that made my reference the 1.1V reference.
No, you don't. The code that you added use the internal 1.1V reference to calculate the actual Vcc (Avcc, but is usually the same). The voltage reference is still the Vcc (5V).
I must say that if you don't know much about software (as I do) the documentation about reference voltages and how to implement them seems very obscure. Or at best vague. I guess there is the assumption of a certain level of knowledge.
Yes, but it's not so difficult, at least if my very simple mind can understand it! Arduino as 10 bit adc, meaning that the value returned by the analogRead() can have 1024 different values, ranging from 0 to 1023. What this number mean? It's not of course the value in volt of the voltage applied to analog in! Here the reference, that is the max value (1023) in volt. So if you reference is 5V, each unit in adc reading is equivalent of 5 / 1024 = 0.0048 Volts, so if your reading is say 347, the voltage will be 347 * 0.0048 = 1,6656 volts. If your reference is 1.1V , the unit is 1.1 / 1024 = 0.0010 volt, so the same read of 347 this time will be 0.0010 x 347 = 0.347 volts.
I still have no idea how or why the software I simply copied and pasted works. But I assume I will learn over time.
To all those who made a comment, I thank you as your comments pointed me in the right direction.
Just to let you know: the solution that you find is working, and is very good and smart one, but in your specific case it's a bit 'overkilled'.