I dug up my MuVo after not using it for a few years, deleted all my music and tried to put new stuff on. It’s a 2GB device but after 200MB I was getting errors from both Ubuntu and the device itself about running out of disk space.
I tried unmounting/remounting; didn’t work.
On a whim I enabled “show hidden files,” and found that when I deleted my music it wasn’t really deleted– it got moved to a “.Trash-1000” folder that still held it all. Once I deleted this entire “.Trash-1000” folder the device correctly reported its capacity.