Telling me I have no space available even though its empty..aargh, very frustrated !

I’ve deleted all the playlists off my sansa fuze and am now trying to re-add playlists and I get a message that I have no space available even though I deleted all my lists.  I’m so frustrated.

Format it. That should clear any residual gremlins and give you a clean slate from which to start over.