Nodders: if you have your songs on your computer then you're fine. Restore the iPod, which as mentioned is like restoring it to factory software conditions (barring a hardware problem on your iPod) and then plug it in. iTunes will consider it a brand new iPod, and will upload the songs to it.
So long as the music is still on your computer, you haven't lost it. iTunes - iPod syncing works only in one direction: from iTunes to your computer. It does not work in the other direction unless you go through some third-party effort.
I can't believe I've had so many iPods. Is there something wrong with me?
iPod 2G, iPod 4G, iPod 5G, iPhone, iPhone 3G