Try updating the firmware one more time.
Follow the manual instructions in this link:
http://forums.sandisk.com/t5/Fuze/Sansa-Fuze-Firmware-Update-01-02-31-amp-02-03-33/td-p/139175
Download the All Regions link, not the updater.
Unfortunately, it may not be a firmware problem. A separate little long-life battery runs the clock (and saves settings while the Fuze is turned off). If that battery is dead, it would have to be replaced in the hardware and no one does that because labor time makes it cheaper to buy a new Fuze.
If you got the Fuze less than a year ago, it’s still under warranty, and you should immediately call 1-866-SANDISK to arrange for a replacement. Otherwise…