It sounds like when the error came up, something had already been corrupted. If you Cancel out of the Restore operation, it should have just aborted and left things alone. Your file system was probably already hosed by that point. Rebooting got your operating system back, but the hard drive contents were toast.
I use a free third-party program called SharePod. It allows you to back up your iPod contents to your PC. In general, it's nearly impossible to do manually that because everything on the iPod is "coded". The titles are all hashed, supposedly so that you can't just copy contents from one iPod to another because of copyright protection blah blah blah.
Anyway, SharePod has a range of options and settings, so what I do is have it automatically create subfolders for Genre, with Artist within that, and Album within that. Files saved to the hard drive can be named by any combination of Title, Track Number, Artist, etc., so I just go with Track Number and Title, since they're already in folders by Album. This also makes it really handy to play tunes from the PC, or (ta-da!) transfer tunes to another iPod.
I'm not sure if sharing the website for it is okay here, but I'm sure a Google search would turn it up pretty quickly. PM for more, if you need it.