Exfat is a different filesystem entirely. No wonder you’re getting corrupted format errors.
http://en.wikipedia.org/wiki/ExFAT
The Fuze is made to work with Fat32. There is a separate, usually hidden partition that holds the firmware, but who knows whether formatting to Exfat destroyed that.
In general, formatting a device that holds its own operating system is shall we say not a good idea.
I’d suggest going to the firmware update thread and following the directions–download the All Regions link, unzip, connect in MSC and send the unzipped files to the SANSA FUZE driveletter . See if reloading the firmware can repair the mess you made.
http://forums.sandisk.com/t5/Sansa-Fuze/Sansa-Fuze-Firmware-Update-01-02-31-amp-02-03-33/td-p/139175
