Sounds like already have your answer. The iPod's hard disk has gone bad and is in need of replacement. You can have Apple swap out the iPod for a flat fee, send it to a third party repair center and have them swap out the hard drive, or you can even purchase the new HD and swap it out yourself using of the many excellent step-by-step tutorials that can be found online.
Here is Apple's pricing.
Google for third party service centers.