I did some of this and was unsuccessful (Disk Utility would not let me reformat the iPod disk). I also updated to the latest version of iTunes (no luck there, either). What ultimately worked was I forced the iPod into disk mode and then tried to run restore from iTunes. It took a few minutes but the restoration worked. I'm currently syncing and am hoping this fixes the problem.