I would say try filling it all with MP3's firstly to see if that causes any problems (even if you have to copy the same songs over and over again to fill it up).
Try doing a check disk on your player's drive and see if that fixes any corruptions in the memory chip. Have a look at this article here:
How to: Perform a scan disk and repair bad sectors.
Let us know how you get on.