Your mp3 player should have come with a CD utility. Most of them do. If it did, on that CD you should find a file with a file extension of .bin or .fw.
That is the compatible firmware you'll need to restore it.
Yes, what i would have done is do a format. I have seen cases firsthand where there appeared to be nothing on the player yet it was 20%, 30% even 50% full. A format always seemed to fix it.
You may have tried to update it with 'mp4' firmware rather than 'mp3'
If you don't have a CD with firmware on it you can try obtaining one here
http://www.s1mp3.org/en/downloads_fw.php#standard
Please read the warnings and download instructions carefully before you attempt to recover your player and only use 'standard mp3 player' firmware.