The power dissipated in a linear regulator is equal to the current multiplied by the voltage drop (P=I*ΔV) 

In my case the output voltage from the ethernet shield is 12V, and the arduino needs 5V, which gives a ΔV=12V-5V=7V

The current draw of my entire setup is appoximately 500mA (0.5A) so the power in the regulator would be about: P=7V*0.5A=3.5W which is way more than the tiny regulator on the uno could handle.

Therefore i've had to replace it with a 7805 regulator in a TO220 casing with added proper cooling... After a couple of months of running quite warm I decided that I was running it too close to it's maximum rating and exchanged the regulator with this step down converter from dx.com Now everything is nice and cool(er).

• TO220 7805 regulator (unmounted) top left
• Step down converter mounted on the Arduino:
  • input (+)= Vin (12V from the ethernet shield)
  • Output (+)= 5V
  • Ground (-) = GND

Arduinos are nice and easy to modify; Since they're open source the schematics and design files (open them with eagle) are freely available, so you can easily learn where to (de)solder :)

BTW: The links to design files and schematics are for the first version of the Uno which is the one i use, for other (current) versions look at http://arduino.cc