what was the fault that initially made you change the battery in the first place?were you losing time etc?
these type of batteries should outlast most computers i think.lifespan is avg of 3-5 yrs.
maybe the motherboard itself is faulty.
if you can enter the bios set up,click "set up defaults" and see if it boots.if you cannot,dig out your mobo manual and see if there are jumpers to reset the cmos.
if having problems booting from the windows cdrom,try making the cd or dvd drive the first boot device in the bios.i guess you have already done so to get as far as pressing R.
not sure to be quite honest sorry.