I had the same problem then tried to put a 2200 µF parallel to my Arduino (and relay) power supply and now my Serial enabled LCD Display is no longer working. It's on but not displaying what it's suppose to display.
I have also noticed that my Arduino no longer run the setup part of the code. When I remove the capacitor, it runs the setup but the LCD is still not working. What could have gone wrong?