Flash the BIOS to the latest version. My K8V Deluxe had the same problem, it would never save, when I reset the CMOS it would always say the BIOS was corrupt, put in the Recovery CD.
If it still is borked, replace the battery (most Radio Shack's carry them).