Hi there-
Run through the steps in this article, and that will take care of "multiple applications using iPod"
http://docs.info.apple.com/article.html?artnum=302538
Then, put the iPod into disk mode, and connect it to your computer.
http://docs.info.apple.com/article.html?artnum=93651
Once you do that, try to format this way:
Open Control Panel
Open Administrative Tools
Open Computer Management
Under Storage, select Disk Management
Find the iPod volume
Right-click on it and select "Format"
You want the format to be set to FAT32. Leave the rest of the settings as default, and make sure that "Quick format" is not selected.
Start the format.
If you're able to complete the format, then you should restore the iPod (even though iTunes usually pulls it up right away)
http://docs.info.apple.com/article.html?artnum=60983
CG