I came across a few sources that claim the atmega has a not-so-accurate temperature sensor.
http://www.netquote.it/nqmain/2011/04/arduino-nano-v3-internal-temperature-sensor/ http://arduino.cc/forum/index.php/topic,38043.0.html
I tried both of these approaches, but both give me 110-112 no matter if I go stand outside or put my finger on the package. Room temperature is around 18C while outside is more like 6C.
The only consistent difference I get is changing between the 3.3v serial cable and 3.6v battery pack. The latter gives readings of 97-99.