Debugging a 16x2 LCD Display on an Arduino
Do you have a diode across your relay? If not the inductive spikes on closing/opening will likely cause problems.  

When you e.g. stop the current flowing through a relay, it tries to keep it going, if there is no route of discharge it will create a large voltage (essentially it will keep rising until it finds a route).
Specifically the formula is V = L(dI/dT). This means the inductor opposes changes in current through it by developing a voltage across it proportional to the rate of change of current.

Try placing a diode across the relay, orientated to oppose normal current flow. 

EDIT - checking the product page it seems it is a "ready rolled" relay in a box with peripheral components added, so it's unlikely to be the above. Even so I would try placing the diode across the power to the relay.
Also make sure your supply is well filtered as mentioned in the comments. Place a few capacitors of at least 1uF next to the ICs and LCD, and a bulk cap of >100uF somewhere (all from power to ground)