Is all your music in iTunes? What you need to do here is to restore (erase) the iPod. You do this by connecting it to iTunes, and choosing the Restore button. This erases the iPod and re-loads its internal software. Then you set up the iPod fresh, as if it were new.