Try reformatting it on a Mac using Disk Utiltity.
Otherwise, I assume you have tried everything here?
It could be an indication or a damaged or dying hard drive. I would recommend doing a disk diagnostic on the iPod's HD using the instructions given by turingtest2 in this older thread. He also covers what the resulting numbers indicate.