Troubleshooting multi-staged multiplexer design
You should look at the output of your multiplexer with a scope and tell the micro to switch between two sensors that are at different positions. You'll see how fast it jumps from one value to the other. If it is too slow, you'll want to adjust the delay between switching and sampling so the micro samples after it has settled.
I'll assume the sensors are pots, and if you have 500 pots you'll want low total supply current, which means high value pots. Combined with the capacitance of the switches, this can make for slow settling.
I'd put a small capacitor to ground on each input, like a 10-100nF. That will get rid of noise picked up by the wires, and it will be pre-charged to the correct value when the ADC is switched to that input, so the output will settle quicker.
Then, considering the quite high ON-resistance of the switches, you could put a buffer opamp between the switches and the ADC. If you use a single supply, a rail to rail input opamp will be necessary, and if source impedance is high it should have a FET input for low offset current. Check the datasheet for settling time.