With every component that you add to the path between the sensor and the measuring point, it makes sense that you would lose some signal. I mean, anything that does not AMPLIFY a signal... will weaken it.
Why not amplify the signal before you do things like send it through a MUX or a long cable. You could use a a single supply op amp like a TLC272 with a 100K in the negative feedback path (with the - input also tied to 5V via 10K resistor) Use a similar pair of resistors for the sensor input (From the + pin, use 10 K to LM35 source, 100K to GND) and use no more than .1uF on the signal wire from the LM35 to GND.
You would then have a x10 Amplifier. (I'm loosely basing this on an instrumentation amp configuration minus the extra input amps. http://www.national.com/an/AN/AN-31.pdf) I've used a similar circuit while testing a Motorola Pressure sensor.
pw