Relay Module and LCD Junk/Weird Characters

Hello all,
I have my arduino powered by an external power supply (not USB), and it uses a LM35, a heating system and a cooling system (switched by a 2 relay module), and a LCD to show the setpoint and actual temperature.

This is my 2 relay module:

I am also using a second Power Supply only to supply 5V to switch relays (grounded with arduino ground) in my breadboard, due to lack of current in arduino supply.

The main problem is that after sometimes when relay closes, LCD becomes garbled with strange/weird/junk characters.
Similar to the picture: http://i.imgur.com/E8ozP.jpg

I’ve already tried to insert a 0.1µF (ceramic) in parallel with a 10µF capacitor across the arduino 5Vcc and Ground terminals near the LCD, and two more in the 5V rail powered by PC power supply. Also, I tried to use a lcd.clear() function before each writing in the LCD. And none of them work.

I could see that if I shake the cabling from arduino GND, it comes back to normal (after removing and connecting the ground). Then, I tried to connect more than one GND from arduino, but then neither shaking I can have my LCD text back.

It does not seem to be a bad wiring issue. Do you know what could I do? Apreciatte, thanks.

I'm not sure if you have one power supply or two..

I've modified the text. But I'm using two: -one power supply connected to arduino's jack connector -one power supply to toggle relay's coil

(GND of both supplies are connected)