you should be able to open up disk utility (in your apps folder on your mac) and format it to DOS format (FAT32)
failing that, you *might* be able to (if your pc will recognize the mac-formatted ipod at all) open up disk manager (in computer management, in the control panel of your windows pc) and format it as FAT32. then you'll be able to install the firmware on it after you've formatted it.