Well, I ran into a similar issue. What happened was I had transfered a mp3 from my linux mp3 library to my iPS that had a filename that was incompatible with the iPS' FAT file system. I use ripperX to convert my CDs to mp3s and it includes characters like '[' ']' and '?' (from cddb) which the FAT fs has problems with. Also, the filenames can be too long. Then I couldn't remove them in either Linux of W2K.
The way I solved it was to use the old DOS command line chkdsk /F. Yeah, this is totally lame, but it was the only thing I could figure out. There MUST be a way in Linux, maybe reformatting??? But this works.
Once you get that working, you may want to use gtkpod to manage your mp3s and make your playlist(s). Just remember, after you sync in gtkpod, exit gtkpod, run mktunes -m /mnt/ipod and umount the ipod. This looks like a hassle, but the commands can be scripted into a icon on your desktop. I have one icon that is a drawer that contains a gtkpod icon and a mktunes icon that I click after I close gtkpod. Make sure you're using the latest version of gnupod.
Hope that made sense and maybe even helped.