lashed , install the MP3 Utilities that came on the CD, or download ver3.68
Here, or ver4.05
Here.
Once installed, there will be a Disk Tools installed in it.
Click on it and chose "LOW" level format.
Next, go to Partition & Encrypt tab, and slide the slider all the way to the left (min), and click on format.
This would rebuild the whole partition and hopefully the problems goes away.
It's not necessary you'll end up with 512MB. It might be a 2GB or 1GB or even 128MB chip.
Lastly, you don't need to worry about the firmware. As normal formatting only clears data in the memory module, not the processor's ROM.