Your conclusion about the BIOS battery is plausible – it’s well known that colder temperatures affect a battery’s operation for the worse.
However, it could also be anything else temperature sensitive. Power supply, memory, etc.
Try leaving the computer on all night and see if that makes a difference in the morning. Make sure you have all power management software disabled first though.
If it still acts that way, then I’d start looking at the quality of AC power you’re getting. You ARE using a good surge protector aren’t you?
If you have a surge protector or UPS, then I’d change the CMOS (BIOS) battery first because it’s cheap. If you don’t have a surge protector, then I’d get a good one ($25-50 U.S.), and see if that fixes the problem. Last of all, I’d try replacing the power supply in the PC. In that order.
If none of that applies, then please write back.