I know that doesn’t help a lot but in my project (see http://lookmanowire.blogspot.com/ ). I use a TMP36 as a remote sensor and only pull the value every 28 seconds (=activate the TMP36) and I get very constant readings.
Did you try to substitute the capacitor adjacent to the TMP36? And is the power supply for the TMP36 stable? Do you have other devices attached to the analog ports?
I disconnected the TMP36 output from the XBee and hooked up my DMM. Values were still moving around. so it is an issue with the TMP36 or something funny with the power.