If a restore to factory settings in iTunes does not resolve the issue, it's more than likely hardware related, meaning you'll need to have the iPod serviced or replaced either by Apple or a third party service.
I would schedule an appointment at your local Apple Store/Genius Bar to have them take a look.
B-rock