I have a similar problem with one HP Laptop (Pavilion dv6) for more then 2 years look here. What I have discovered so far:
1) Buying another battery doesn't fix the problem,
2) Taking out the battery with the cable connected also doesn't fix it,
3) I have to be careful not to disconnect the power cable when the laptop is shutting down,
4) I have to be super careful not to connect the power cable when the laptop is booting up (but connecting it after the boot seems ok),
5) I got more successful boots with the power cable disconnected,
6) I tried some grub acpi configurations without success.
So I've settled. The two most important steps seems to be the numbers "3" and "4".