I know that this thread is oldish, but I recently purchased a MuVo128 and felt that I should add some of my experiences as well...
Firstly, contrary to what catskul said in the first post, you should mount the device as vfat, not msdos, to enable 'proper' long name support. I found that if you mounted the device as msdos and then copied a file with a non 8.3 name to it, it wouldn't do anything when you tried to play your files. Mounting as vfat fixed that problem and removed the need to rename files during a copy.
Secondly, I've come across an issue with Gnome(2) and in particular the Trash feature. Specifically, if you are removing files from your MuVo using Nautilus, make sure that you are deleting them and not just moving them to trash. I was pulling out my hair trying to figure out why I only had five or six files on my MuVo, but seemed to only have a few megs of free space left before it finally dawned on me.
This last could also be an issue on other OSes or DEs that use a trash system.
