If you bought it as a 4GB player the problem is most likely memory chip related.
At present these players only support a maximum of 2GB but some manufacturers hack the chips so that they read much larger than their true size. In some cases 4GB chips have in fact been hacked 128MB chips.
Hacked players tend to run fine for a while but as you start loading more and more files or add and remove files they start playing up, generally with file corruption, player restarts and errors.
Once you start having problems you need to format the player which will remove the hack and your players memory will then read it's true size.
They can however be difficult to format so if you have trouble try this method
HERE.
Once you have got the memory reading its true size you should not have any problems.
If you want to verify your memory chips true size you will need to open the player and check the serial number of the chip against
THIS list of Samsung and Hynix chips.