Its possible that there's an issue with the database not refreshing on the player. What you'll need to do is delete one of the files in the System folder. Normally the system folder is hidden so you'll need to enable hidden files and folders. If you haven't already done so or don't know how, here's how to do this:
Explore the player through My Computer,
Go to Tools
Select Folder Options then select the View tab
Now scroll until you see Show hidden files and folders and click the radio button next to it.
Click apply and then click ok

Now again open the system folder, but here's where I'm going to need you to stop. I can't remember the name of the system file that you need to delete in order to refresh the whole DB structure.
If you'd be so kind as to tell me what the names of the files that you see in the System Folder, I'll let you know which one to delete. It has to be the right file, or you'll wipe the database clean.. as in format and we don't want that :)