Maybe my post wasn't clear enough, I did solve it. In my case with:
gsettings set org.gnome.settings-daemon.plugins.power active true
I saw the battery icon before login, and other users on my laptop had it too, just my user didn't. I then looked at what was different between those users and realized I had once set the above to false for my own user (in an attampt to stop the screensaver and power saver from turning on).
This is with Gnome 3 on Fedora 16.
While this might not be the solution for the problem other people have, at least they should check the value of this setting, because clearly if it is set to false the battery icon doesn't show. So while it is a condition, it's maybe not a sufficient condition.