I've also had this problem after replacing a battery. I couldn't find a package called "advanced-power", mentioned here. Reinstalling "battery-icon" didn't help.
After long trials of reboots (and auto-off because of apparently empty battery), here's what helped: I tried to reflash the zImage.pr13 openmode kernel, but flasher complained: "battery status to low, charging.. 2%.." - then I knew it was charging at all. I aborted flasher before it reached the needed 11%.
Then I bootet again, and the battery symbol didn't show 0% like all the time, with or w/o charger, it showed the charging animation (with charger) again. Then I did "apt-get install --reinstall battery-icon", and after restart that service, it showed 4%