It's an interesting problem to solve.
Is the ADC returning obviously spurious results or are they too sneaky to filter out? I.e. would it be possible to make assumptions for the direction of the trend and ignore values coming from the ADC that are "obviously wrong?"
Also, I've never written for ATmega; is it Assembler, C, or some higher language?