Answer's a bit late... over 2 years, but I thought it may be useful to others having similar issues.
I mainly work with these iPods and over time I noticed this problem was recurring over a large amount of hard drives. So I decided to purchase a 1.8" IDE to USB adapter. They allow you to connect the hard drive directly to your computer without the use of the iPod.
Doing so showed that the hard drive needed formatting as it was damaged. I formatted and then again it displayed the same hard drive size around 3-5GB.
I then tried a more drastic restore, go to control panel, then administrative tools, then computer management, on the left you will see a drop list of options, go to storage then disk management. Here my hard drive was displayed as it's real value of around 18-19GB but 14-16GB of it was unallocated.
You can allocate it using windows but I already had a program that manages your Hard drive called Mini Tool Partition Wizard so I loaded that up and there it was again, the same unallocated space. I deleted the 3-5GB that was allocated making it 17-19GB unallocated. Then you allocate it. Go back into my computer and you should now see the hard drive with it's real value, Quick format it to set it back to the allocated letter windows prefers. Insert it back into your iPod and connect it to your computer to restore using iTunes.
You'd be surprised how many iPod hard drives I get just needing this simple fix.