Have you considered the possibility that you're feeding a higher voltage than 5V into the micro from one of the other pins? Say, "Temp IN" or "PWM out"? (In the case of "PWM out", just try desoldering the transistor and see if that does it - you might have blown the transistor, which is shorting "PWM out" to the gate, and thus into the micro)
Because it sure sounds like you are feeding a higher voltage in; if you're seeing >5v and impossible power dissipation in the circuit when your regulator only gets a little power, and then the problem goes away if you remove the chip... I'd vote on the IO pin protection diodes conducting a higher voltage to Vcc on your micro, which backfeeds the regulator (which may well blow it too!).
Are you testing the circuit with only two wires hooked up to the board, namely Vin (to the reg) and gnd? If not, disconnect EVERYTHING else, including the ISP programmer, and see if it still does it.
Edit: Note that if your chip has ever done it (conduct enough power to heat it up via the protection diodes), it may be blown and will continue overheating even with the fault cleared.
Also, if this doesn't solve it, check EVERY pin on the micro for shorts to ground or Vcc - even if it's not programmed, it might (not familiar with AVR) be driving some pins.