This is a symptom of a battery starting to get old. Its inner impedance is increasing, and the reboot sucks more current out of the battery than for normal operation. What this translates to is that the voltage will drop a lot due to the extra current drawn during reboot. A new, healthy battery can handle that with ease (less internal impedance) and only drop a little bit. An old battery can get floored. It will recover after a while (because the current drain stops when the reboot is finished), but if it's bad enough the voltage will drop to a level which can't sustain the device. So you can only reboot when the battery is fully charged.

The only remedy is to go out and buy a new battery. Which sometimes can be easier said than done - most of what you find in shops are old (been on shelves for years) and stored in non-optimal conditions, e.g. too hot.