arduino + LCD fades until other applications are done.

We have a LCD display and 4 switches to turn on relays for certain applications. I'm using atmega1280 and the problem that we have in our project is that the LCD display would fade every time the switches were powered. Once the switches are off, LCD display goes back to normal.
Another problem is that when the switches are pressed, the response is slower unless it is firmly pressed.

Is it because there is not enough voltage is supplied with everything ? Or a current problem?

I am powering the arduino through USB cable btw, which is normally 5 volts I think.

How can I solve this issue?

Will using a higher external power supply (9-12V) solve this problem?

do you have a part number for the relays? and can you post a quick diagram of how its connected.