I had a similar problem with a 16x4 LCD display when the Arduino was also controlling a SainSmart opto-isolated relay board, 2-Channel 5V Relay Module | SainSmart – SainSmart.com. Everything worked fine with the relay contacts unconnected. But when the relay switched an inductive load (a 24 VAC power relay), the display garbled. No amount of power isolation and filter capacitors helped.
What solved the problem was a snubber (capacitor and resistor in series) across the SainSmart relay contacts. I used an expensive prepackaged Cornell Dubilier EMI/RFI filter (http://www.digikey.com/product-search/en?x=0&y=0&lang=en&site=us&keywords=338-2580-ND) for neatness, but a garden-variety 0.1 ufd capacitor in series with a 47-ohm resistor would probably work just as well.