Try the following (on your Mac, obviously with your ipod forced into disk mode):
1) Download the "mbr" file for your ipod from the IpodConversionToFAT32 wiki page and write it to your ipod. i.e.
dd if=mbr-video60gb.bin of=/dev/disk1
(assuming disk1 is your ipod)
Now disconnect it from your Mac and reattach it.
2) Download the appropriate firmware image file (a .ipsw file) for your ipod from this page:http://www.felixbruns.de/iPod/firmware/
The .ipsw file is in fact just a zip file. Unzip it using the command-line unzip program:
3) You should now have a Firmware-X.Y.Z file which you need to write to your ipod. Do this s follows:
dd if=Firmware-X.Y.Z of=/dev/disk1 seek=63
4) Finally, format the FAT32 partition as described in the IpodConversionToFAT32 page.