Download the latest iPod updater from Apple:
www.apple.com/ipod/download/
Install this, then reformat the iPod. Depending on what generation it is, you might need to have your AC adapter close by. (It also depends on what platform you're using.)
If it asks to 'reflash your Firmware' disconnect the iPod and connect it to AC power. (Or just use your Firewire if you're on a Mac or a PC with it.)
Let the iPod install the software (you should see a progress bar underneath the Apple logo) and restart for itself before finally reconnecting the iPod.
If my steps aren't entirely clear, you can PM me
Also, if you could leave your specs, that might help too.