I have spent at least two weeks already trying to tidy up all my mp3 files before loading up everything back to my iPod. And it's still not finished.
The main issues I've had relate to metadata and file formats. Such as:
1. incomplete metadata. In a lot of cases the only information available is the filename, which always has the artist and song title, but occasionally has instances of track number, album title and genre. I've started using the excellent mp3tag, which has the "filename to tag" function, allowing metadata fields to be filled in based on information in the filename. Just right-click on the file, select the function you want (it also does "tag to filename", etc), select or enter the format of the filename info (eg, "%artist% - %track% - %title%"), then it will fill in the relevant fields. It works not just on mp3, but also on m4a, and FLAC formats.
2. inconsistent information. In some cases it can be as simple as some files missing a '.' at the end of the name, ie, N.E.R.D vs N.E.R.D. In some cases some files in the same album are tagged with a different genre. Or some, but not all files have a particular field filled in.
3. audiobook mp3s not identified as audiobooks by itunes/ iPod. This could be just because I've been to lazy to actually read up on the iPod documentation - which is probably in the CD that came in the iPod box - but I didn't know that your files need to end in *.m4b so iPod treats them as audiobooks and excludes them from any song shuffling that might occur. I've just been putting up with getting the occasional audiobook track mixed in when I select Shuffle Songs and just clicking to the next song. The problem is, the audiobooks I have are in mp3 format. So I need to convert them to AAC, then rename their file extension to *.m4b.