I would have said cmos battery worth a try as well, maybe a silly question, but did you remove the power lead and reset the cmos via jumper as well after putting in new battery?
I had a problemn with a pc at work, where a sata hd was installed and it kept failing to boot. i couldnt work out how to fix it so i messed about with bios and found that changing storage controller to ide worked. but it wasnt recognising hd in bios at all at first so prob not gonna work in your case and slightly random..