31 GB of "Other" on my iPod Classic 80GB

Connect your iPod, in iTunes select it under DEVICES, move to the right and select the Summary tab and then click on Restore.

This will remove all data from your iPod, Resync your music, etc. after you are done.

Just to add to this comment, also make sure that you're not manually managing your iPod otherwise you'll lose everything you've stored on you iPod.

Definitely restore to get rid of the junk.

It does not matter if you manually manage or autosync your music, all will be removed when you restore. If all of the 3000 songs are in your library (which is backed up, right?), then there will be no problem putting it back on.

The 31Gb of "other" will probably be lost duplicates of your music library. If your 3000 songs are also on your computer then you can restore the iPod, if you've been manually managing your iPod and addding in files from different locations, or deleteing them from your computer once you've put them on your iPod then you will need to recover these files before you restore or they will be lost. Restore deletes everything on the iPod's hard drive and then rebuilds a clean version. Should you need to recover any tracks check out this post from Zevoneer for some iPod recovery options.
http://discussions.apple.com/thread.jspa?messageID=6273675&#6273675

tt2

So you killed your iTunes library as well as trashing your iPod?

If all you've got left is random media files with meaningless names in meaninglessly named folders then you should copy the whole lot to a large external drive, put them into a folder called, for example, "Trashed", then create a new empty iTunes library, set it to manage the music and copy files into it's library, import the "Trashed" folder and iTunes should create a more normal Artist/Album/## Track structure in the iTunes music folder. Your playlists will alredy be lost since they were in that iTunes library you seem to have trashed. Also most video files don't carry tags so you may have to recreate the information for these.

tt2

Use Windows Explorer and drag your iTunes folder to the external hard drive.

Ok - I think I'm getting the picture now. Do I take it you'd like to backup your iPod "as is" before restoring in case you don't like what happens and want to go back? If so SyncToy is the tool for you...

*Fast backup for iTunes library (or iPod) (Windows Only)*
Grab SyncToy 2.0, a free tool from MS. Use it to create a backup copy of your iTunes library & any other media folders (or your entire iPod) onto another hard drive or network share. After making the initial backup copy use SyncToy to periodically synchronise the backup copy with your library (or iPod) and only the changed files will be copied saving lots of time.

Generally speaking it's only the iTunes library & all relevant media folders that need to be backed up. What iTunes puts on the iPod is derived from your library if you're syncing which means you can restore the iPod without losing playcounts etc. and don't need to back it up before restoring. That said iTunes doesn't backup your iPod settings or game scores. Tools like iDump are really for recovering the songs from the iPod when your computer dies and you failed to backup all the tunes in advance.

tt2

Going all the way back to your original post if all you've done is dump some redundant data onto the iPod which you now want to remove it should be possible to work out where it is. The standard folders on an iPod Classic are Calendars, Contacts, iPod_Control, Notes, Photos & Recordings. Any other folders or files in the root level are safe to delete.

tt2