|Does the posting screen show the cdrom(s)? If it's not seeing them it'll go to the HD and attempt a boot there.|
Maybe the battery or holder has a bad/loose connection. Or maybe it's in backwards. To test that DON'T just turn the battery around. Check the manual or polarity indicators (+ -).
Can you tell if it's holding the time and date? If not, it's got to be a failure with the cmos somewhere. Well, either that or it's not being saved correctly.
With some motherboards you can hit a key (not the cmos/bios setup key) to alter the first boot device. To temporarily get around the problem--and if the motherboard has that capability--you can boot from the CD that way.