Does it show up at all in Disk Utility on the Mac?
Does it show up if you open the iPod Updater utility on either machine?
If not, then possibly the partition table is messed up. In that case, you'll need to do some low level repair in order to restore the partition table -- unfortunately Disk Utility will not do that for you. The exact details of the repair depend on whether you want it to be FAT32 formatted (usable on both PC and Mac) or HFS (Mac only).