If you use VDD as the voltage reference for your AD then it is most likely a not stable powerline. I know you said battery and voltage regulator but have you tried to measure the VDD with an ocsillocope?

If you really need to get high accuracy reading you might have to consider an external high precition voltage reference. That one you can connect to the VREF pin and then you can set up the AD to use that one.

Also if you are switching other stuff while doing the measurement it might affect the power supply to the pic as well.

I would start with making sure the power nice and clean and batteries are not the best source when you start doing new designs.