Not enough space for music DB. Please clear up 90 MB and computer won't recognize my Fuze?

I got the same error a few days ago.  I’ve reformatted my 4GB Fuze about 3 times now, and my computer seems to think it’s a completely new “removable disk”.  Also, I’ve lost the ability to use playlists on the Fuze - even through I synce my music as playlists through Windows Media Player, the playlist folder is empty and the music just shows up in its individual album folders.  How did that happen, and is it fixable?