-----UPDATE-----
Hey everyone & Cattledog,
It appears that everything was working when relays were disconnected completely.
Once I have connected relays with a separate power input, as per the diagram from my second last message, and the problem is back.
It appears that when relays are disengaged the problem occurs.
After having a read on this, it appears to be an EMI problem.
In terms of solutions, people suggest isolating circuit (which I have done), using capacitors and varistors get rid of the current (?) that is being sent back to Arduino when the relay is disengaged.
Unfortunately even after reading on about it, there is no clear solution that I see (probably due to my lack of knowledge on the subject).
Once again any help is appreciated!
thank you!