ok, I'm coming from a mac standpoint here, so bear with me.
You'll need to get the songs off of your ipod first and into a plain old folder.. um directory, on your hard drive. You can do this with a program designed for just that.
There's tons of commercial and shareware progs to do it, but freeware seems scarce. I only found one freeware title on VersionTracker, called
PodLift, but if you hunt you might find others. Maybe somebody with the PC version would be so kind as to suggest something better, as I've had no experience with itunes utilities on the pc.
Once you've got your ipod content on the hard drive, I'd assume you could just drag the whole folder into itunes (this may work differently on a pc than a mac, dunno.) If you've set iTunes's preference to "copy files to iTunes music folder when adding to library" and "keep itunes music folder organized" it should slot everything into a new directory structure by artist/album. After that's done, delete the directory you first created, since all your songs are now in the "sanctioned" itunes folder. You should be able to sync normally after that.
Hope that works ok.. sorry I couldn't be more pc-centric.
EDIT: HA! By the time it took me to type all that out your problem was already solved. I blame it on my kids!