Perhaps the simplest way is to wipe the mp3 player clean and then copy everything across. However, it is clear that this is a very in-efficient way to go about things. After some searching (and question asking on superuser), the method I am now using is as follows:
rsync -rlpuv --progress --include "*/" --include "*.mp3" --include "*.ogg" --include "*.wma" --include "*.flac" --exclude "*" ~/Music/ /media/E100/MusicBasically, this copies only the music files from my library to my mp3 player, and ensures that the creation time is set to the current time so that the mp3 player reload the database correctly.
Now I don't have to wait for half an hour for all my files to copy over, and the database on the mp3 player updates much faster as well.