A new battery didn't fix it?
The next step would be to set the BIOS to defaults and disconnect all hardware, see if it gives you the same error. If no error, re-connect one by one until you get the error again. Then you will have diagnosed a bad piece of hard ware.