Isn't iTunes just showing you its own way of organising things on the front end. In the background it stores everything in its own choice of database using the tags of artist/album/track/style to then present it as you expect on your iPod?
Regardless, if you've all your tunes on the copmuter anyway can't you just wipe the iPod and sync afresh?
DISCLAIMER : I've not touched an Apple product since 1987