The smallish SOT-223 v.regs are only good for about 0.3-0.5W dissipation.
Don't forget that the tab on the top is designed to act as a heat sink. So you can actually get more dissipation than 500mW. In fact, we need to go to the datasheet to find the real numbers.
The regulator used on the Uno is a NCP1117. http://www.onsemi.com/pub_link/Collateral/NCP1117-D.PDF
Which according to page 8 of On's datasheet the SOT-223 the maximum power dissipation at 50°C with the minimum sized copper pad is 650mW. The Rj is 85°C/W.
Three things note:
1) The "minimum pad size" is 3mm x 3mm
2) The graph is drawn for ambient of 50°C (2X room temperature)
3) Most arduino projects are run in free air at or near room temperature
Looking at the PCB layout for the Uno, the regulator is attached to a ground plane. The ground plane is ~10mm x 15mm uninterrupted. (It is larger than that, but that's where other traces are running.)
Going back to the On's graph, let's look to see the maximum power dissipation for 10mm, which is conservative. That's nearly 1W. Again, we're talking about an ambient of 50C.
Alternatively we can use Rj from the same graph, to can calculate maximum power dissipation at room temperature:
Pdmax = (Tjmax - Ta) / Rja = (175C - 25C) / 100 = 1.5W
Imax = Pdmax / Vdrop = 1.5W / (12V-5V) = 214mA
Personally I have been able to draw up 250mA through the regulator before it started shutting down, which matches the above math.
This is also why we so many people who post saying: "My project works fine on USB but not on 12V!"