Could be a noise issue. Have you checked your wiring and power supply to rule that out? I.e. there are no other relays, other things that are potentially interfering with the ADC?
You could also try putting a small capacitor across the output to smooth the response and resist spikes. Naturally, such a cap will slow the responsiveness of the sensor. You could also filter the results in software as suggested above. One technique I like using on (relatively speaking) slow moving signals is decimation. You end up with better accuracy and it filters noise too. See the Atmel AVR white paper for more info on this. Plus, you get to learn about bit shifting.
Last but not least, depending on the speed with which you are switching channels on the ADC, there can be problems also. If you left the ADC pre-scaler alone, this should not be an issue.