Interesting. After deleting the files from the Clip, and reloading them with the corrected ones, did you get a “refreshing database” message?
Try this for an experiment. Connect the Clip in MSC mode, and delete the mtable.sys file in the root directory, then unplug. After the refresh, are your songs now available?
Bob 
