I have the same problem with the TMP36.
I built the lovometer from the Arduino Starter Kit book, as a way to understand how the temperature sensor works, in order to use it in a small weather station.
The first day it gave me reasonable values for the baseline room temperature (28°C, it seemed a bit high but the day was indeed hot); today I tested it again and it gave me 32°C while the day was much chillier; later it even showed temperatures around 55° C.
I want to use it as a weather station, and apparently some other people use it that way and it works great; so what have I done wrong?