I've put a bunch of music on my shuffle via rhythmbox, verified that the shuffle would play it by ejecting and playing it. Then I wanted to clear the music off, so in rhythmbox I selected all the music on the shuffle and told it to move the music to trash (my only delete option). All the music "went away" according to rhythmbox, and the shuffle itself gives the flashing lights as if there were no music on it, however the used disk space doesn't change and I'd quickly be unable to put new music on the device even though it thinks there is none.
Yep, you need to empty the trash before ejecting the device to get your data back. See: http://bugzilla.gnome.org/show_bug.cgi?id=346434
I've attached a patch there. Testing it would help. Waiting for feedback from upstream now.
I'll test when I can this weekend, I think I have an ipod somewhere around here. THe shuffle is back at the office (whoops).