Uno with LCD acting strangely - power issue?
System resets can be caused by power droop and by noise at the Reset pin, among other reasons.  The problems mentioned could be due to power issues, or to electrical noise, or to wiring issues.

The total current draw apparently could approach or exceed the 400 mA mark mentioned in the question.  With all four relays on, and coils drawing 50 mA each, that's 200 mA.  LCD backlight and Arduino current make another 100, after which the ethernet shield could bring the total above 400 mA.

However, having the problems persist even with an external supply in use would suggest the root of the problems isn't power – if, of course, the external supply actually is supplying power directly to some of the peripherals, rather than via the regulator on the Uno.

When relays switch, they typically produce an electrical noise pulse.  If this is the problem, it could be mitigated using ferrite beads, chokes, noise filters, etc.  Using a separate power supply for +5 V to the board also should help.

Wiring issues include ground bounce and ground loops.  If you are using a breadboard, there may be poor ground or power connections.  Check that the grounds of peripheral devices and external supplies are solidly connected by decent wire and/or connected at a common point.