My laptop (Fujitsu Siemens AMILO PI 2550) sometimes falls out between 10 seconds to 2 minutes on a cold boot when it is not connected to the powercord.
It doesn't seem to matter how many battery I have left.
I have tried to fully recharge my battery a few times but the problem remains. Also the problem won't happen if I have connected my laptop to the powercord and remove the powercord after 10 minutes or so. It also happens when I recover my laptop from standby.
Seeing that it is occurring when booting up, chances are that it is an issue with the battery. It could also be an issue with the contacts/connection from the battery to the motherboard. If you've owned it for less than a year, I'd get in touch with Fujitsu and see if you can send it in for them to have a look at, i.e. the factory warranty should cover it. If it is out of warranty, it still wouldn't hurt to get in touch with them to see if the issue can be diagnosed so you know where to go next.