If I understand you correctly, if the voltage is steady using a voltmeter to read the LM35 output but your readings once massaged thru the PIC are unstable then I'd blame the code or the inability of the PIC to read the output.

In post #2 Acetronics says you are very close to minimum reading and that may be the case. He also suggests a different sensor which may be what you have to do to get an accurate reading.