PeterH:
If your requirements are so close to the resolution of the ADC that a variation of one or two is important to you, you probably need to use a more precise ADC.
Under battery power the ADC is pretty well behaved (certainly noise below 1 lsb) - I suspect this is power supply noise - is the PSU a switching one? Extra decoupling can help.