Why is my analog temp sensor's signal so unstable?
The most common error people make with the Arduino vis analog reading is assuming the Vref is exactly 5V.  This is seldom the case, especially if you using the USB port to power the board.

USB is a relatively high impedance power source and doesn't take too kindly to changes in load (such as flashing an LED) and the voltage can fluctuate quite a lot.  You should adjust any calculations to do to use the real Vref (Vcc) voltage and not assume it's exactly 5V.  The simplest way is to measure the voltage with a DMM when you have all your components connected up.

A better way would be to use a precision voltage reference chip to provide a stable reference voltage to the Vref pin of the Arduino.

Also: have you decoupled the power to the sensor?  I.e., placed a capacitor across the \$V_{CC}\$ and \$GND\$ pins (100nF for the device, and maybe 2.2µF - 10µF for the remote connection to the power).