Hi Prerna
For the LCD decoupling caps, start with a 100nF capacitor and connect this between the Vcc and GND pins of the LCD, as close to the LCD module as possible, i.e. directly on the module pins. (the 0.1 inch header.)
It is possible that an LCD operation is not setting the register select (RS) line when it should. Is the LCD initialized again when the push button is pressed? It sounds like something is happening when the push button is pressed and that is triggering the corruption, i.e. what is different between normal operation and when the push button is pressed? That's the key.
I doubt unshielded LCD lines is the problem. Do some measurements on the LCD lines with an oscilloscope (when the push button is pressed). Usually with LCDs it is timing that is the issue, i.e. not observing the bus times when setting data and enable lines etc. (I assume the cable to the LCD is also relatively short, i.e. only a few inches.)
Good luck.