Memory space problem after deleting files

I was trying to take an album off my sansa clip+ to replace it with another, but every file I deleted opened no available room to replace it. Somehow my player thinks it has lost a huge amount of space. I can’t put any new music on as it says it can’t fit, and it now only has about half of what it did originally. I’e tried rebooting it and reconnecting it to my computer, but nothing is working. How can I get it to reformat so that it acknowledges that it really does have a ton of free space on it? This is extremely frustrating, as it happend 2 days after I got it. Ugh.

Settings > System Settings > Format on the Clip+'s screen.

NOTE: This will erase all user-installed content in the memory. You will need to re-load everything.