By restoring, I meant plug it into iTunes, and clck on the Restore button in iTunes (PC or Mac iTunes, not the iPod's iTunes.
This deletes everything on the iPod, resets everything with iOS4, and then syncs everything back. You might want to let it sync before restoring, just to be sure you don't lose anything.