When you initially set it up on the mac it'll have been formatted to HFS+ (mac filing system). Windows won't be able to read it.
If you'd set it up on the PC first, then it'll have been formatted to FAT32, both windows and the mac will then be able to read it.
There maybe (this was the case, not sure anymore) issues with with upgrading the firmware. If you had a PC iPod then you had to update firmware on a PC, and likewise with the mac. Trying to "Cross" upgrade would result in a format.