The original Fuze has a song capacity of 8000 tracks.
To attain this capacity, first be sure that you have the latest firmware installed on the device. The original Fuse was produced in two versions, with an updated processor, so first check your version via Settings > Info. The forst two digits of the firmware designator will tell you if it is a version 1 or 2.
Here is the firmware thread for you. Note that if you install the Sansa Updater listed in the thread, you can also update the device automatically. The manual process is also very simple, just be sure to unzip or extract (Windows 7 has an automatic “ectract” feature) the firmware file prior to installation.
Both the odd Windows Media Player message, and the capacity issue, should be solved by using the built-in format command on the player itself (this is different from the Windows format command from the PC). Before doing this step, be sure that you have backup copies of your music, as it will clear the internal memory portion (not the microSD card) in your device. You will find the command at Settings > System Settings > Format > Yes. This will optimize the internal memory of your device. You will only have to do this once. In the future, you can format from the PC if needed.
I would recommend removing the microSD card during this process, then mount it afterwards. The music database will refresh, reloading references to your music files on the card, this time from scratch. One additional thing that will happen is the Windows Media Player information on teh device will also be built anew when you sync with Windows Media Player.
Oh, and one last thought, definitely check the 32GB card as mentioned above. Sadly, the 16 and 32 GB cards are notorious targets for counterfeiters (as folks look for the larger capacity cards). The h2testw utility is great stuff.
The Secure Digital part of the micro SD card is often overlooked. As long as it is mounted in your Sansa, and you use MTP mode, the files will play on your device even if protected media. The device recognizes the card as yours, and files transferred between your PC and Sansa have matching keys (if encrypted / protected). Of course, if the files are basic MP3, they will play regardless.