I tried an iPod restore. It did not work. I put the iPod into diagnostic mode, and ran the hard drive diagnostic plus some of the other tests. All the tests passed.
The solution? I hooked the iPod up to a Windows PC and did a Restore. This formatted the drive with the Windows file system. Reconnected the iPod to my iMac. Presto, I was able to sync my entire library again. Saved my self $500 Canadian, as I was going to buy a new iPod if I could not get it to work.

