Sorry, no good news . . . there is an on-board FORMAT function on the Fuze, but since you’re getting the error message you can’t get to the point in the SETTINGS menu to activate it.
You need a Windows machine to format the device. DO NOT attempt to format it using your Mac. If you can use a work or friend’s machine, you can force MSC mode by sliding the power switch down (HOLD) and pressing & holding the center button down while plugging the cable (already connected to the computer) into the bottom of the player.
Next open a Windows Explorer pane by pressing the Windows key (between the Ctrl & Alt keys on your keyboard) and the ‘E’ key at the same time. Note that you may get a pop-up before this asking what you want Windows to do with this device that was just connected. If you do, select ‘View Files with Windows Explorer’. If it opens like this, you’ll need to go up one level where it shows the Fuze under Devices With Removable Storage.
Now right-click on the Fuze’s icon and select Format… from the context menu. It should come up as a FAT32 file system by default, but double-check it. And don’t select Quick Format. Click Apply or OK or whatever it needs to continue the formatting process. This will erase all content you’ve put onto your player giving you a clean slate to start over with and freeing up all your available memory.
Hope this helps.