Reading the responses here, most of the posts are correct in that they are recognized diagnostic procedures, but many are not addressing your problem.
Updating software/hardware to fix a problem that was not caused by a hardware/software change can only complicate things, expecially playing with a flash BIOS. BIOS flashing should only be done on an error free pc for improved utility patches -or- for compatility for new hardware like a processor. If its not broken, dont fix it. The chances your CMOS info is corrupt is very slim and a bad battery would present differently like not keeping time settings
windfish113 + darrenforster99 posts imo are the most applicable for this type of problem. A PC that reboots instead of powers off can be an indication of an incorrect ACPI setting in the BIOS or incorrect header wiring on the motherboard from the front panel. Trouble is, most OEMs (Dell, Gateway, HP) come with a ribbon to a plug on the motherboard instead of front panel pins+wires. So a poorly seated (wiggled out), bad or pinched cable can be a small possibility.
Power supply issues can be intermittant, or cause bizarre pc behavior, but i would think it would reboot while using the pc and not when you're trying to shut down.