Try going to a friends house with a windows iPod? Then start the iPod in disk mode and do a restore using their pc and use your mac to put your music on by copying and pasting it into the iPod itself from my computer (or whatever macs call my computer). Should be fine after that...
PS - someone correct me if I'm wrong!