Also note that the “Not enough space for music DB . . .” error message does not always (in fact rarely) mean that the memory is full. It usually means there is some corruption in one or more of the files. This can sometimes be found and fixed by running ChkDsk (or the mac equivalent) on the drive, but formatting will clear everything and optimize the memory clusters. You will have to reload everything after formatting, and I would advise running ChkDsk on the files while they are on your computer before transferring them back over to the player to prevent the problem from occurring again.
This also seems to occur more in MTP mode than in MSC, so unless you’re using a subscription service like Rhapsody or using DRM-encrypted files that require MTP mode, I would advice using MSC on the player. Never use the Auto Defect mode. And if you’re using a mac, you should be using MSC anyway.
Here is the SanDisk KnowledgeBase article on the subject: