When you replaced the battery did you reset the date/time in BIOS? If you've got the mobo manual go thru' it whilst in BIOS and check everything is set correctly. If you did reset the date etc. does it lose it again after a shutdown? if so maybe your new battery is also a dud.