Plug the iPod in on the Windows side and Restore it using iTunes to convert it to FAT32.
Formatting the iPod using Disk Utility won't work - iTunes on Mac will force you to restore it to Mac format before it'll work again. Restoring it to FAT32 in Windows won't cause this problem.