I doubt it's the BIOS/CMOS battery. Even if the configuration was lost, most BIOSes these days will autodetect IDE devices (HDs and CD/DVD etc). The boot info (which partition to boot) is stored on the HD itself. The boot order wouldn't prevent devices from being found.

I'd try what Unne/NM suggested, though as you originally suggested, it could well be the motherboard.

Just wondering, were there any problems at all when you tried linux? I'm assuming you installed it to the drive, and not used something like Knoppix.