Is your meter good enough to measure 10 mV changes? Because that is how much the voltage changes per degree C. Per degree F is more like 5.5 mV.

Also, if your 5V has too much noise on it, you will not see the small voltage changes either. So make sure that the voltage being used to power the sensor is really clean or filtered well.

With the resistor you are using, you are only pulling 600 uA of current. If you measuring device does not have a very high impedance, it will also affect the output voltage. So try lowering the resistor to 2.2k or even 1k. You will still only be drawing a couple of milliamps.