I have just purchased a Clip and as soon as I turned it on, the message is displayed. I tried to format it from XP and Vista with the same message “Windows cannot format the device”.
I cannot access the Menu of the device as it shutdowns after displaying the message.
I also tried with the Sansa Updater but didn’t work.
The “not enough space for music DB” message will occur when the internal memory is so full of music that there isn’t enough space (4MB) for the Clip to build the song database. Because you likely don’t have any songs on your Clip (except the 4 that the Clip is delivered with), you probably have a hardware problem … return it.