Measure the voltage of each your fully charged cells with a multimeter, add the two voltages together. You will have a figure somewhere in the 2.4V to 3.1V range. Anything other and your cells are duff.
Next, fit them to the camera, and check what CHDK reports, you will see, either the voltage measured by the camera matches (in which case your cells may be suspect, with a high internal resistance), or you will see the voltage measured by the camera differs.
If the camera suggests the voltage is lower than your measurements, then there is some voltage drop caused by dirty contacts in the camera as previously suggested. The contacts may look perfectly clean to the eye, and still have a film of oil or oxide on them, and has has been pointed out before, this is the most likely cause of your issue.
... also check out this possible fix...
Canon Powershot - Low Battery Icon FixIf the measurements from the multimeter and the camera match, and are within the range allowed by the camera, and you are certain the cells are good, (i.e. new Genuine quality named brand cells), and your particular camera reads exactly the same voltage, but still suggests they are flat, then you do indeed have a lemon on your hands.
If you see some other result, post it here and we will analyse it.