I have a similar problem with my new 8GB Sansa Clip.
Once upon time - after using all the treasurous features fine - I found that startup sequence of the player lasted significantly (up to 4-5 or more times) longer than initially. At the same time - and even crappier, the nice “resume from where you played when I turned off” feature was suddenly lost and the player seemed to restart every OFF/ON cycle from the same state. Crap, I thought.
So I tried to remove some of the music files I stored so far to reduce the whatever work for the nice little gadget. But, it isn’t possible, nor in MSC or each other mode to erase the music from the device again. Also I tried to format the drive, same result: After OFF/ON all is there again. I tried that with the players internal formatting function as well as with MS Windows XP, as well as with liunx based tools gparted, fdisk, parted and ‘rm -rf’. Even "Delete song"from the normal menu seems completely ignored after next OFF/ON cycle.
So what should/can I do else?