If you get a PC to format your iPod, it will work with both PCs and Macs. If you get a Mac to format it, only the Mac will recognise it.
If you don't mind losing everything on your iPod temporarily (assuming it's all backed up) then plug the iPod into the PC, run the iPod software updater software and restore the firmware. 🙂