Just a suggestion, but maybe if you opened it up and put the drive into an external enclosure you could run checkdisk or something on it, in case there is in fact a hard-drive fault (I mean, even if a Mac can restore it, I think it might still be faulty, just not in a way that produces an error for the restoration process on a Mac - especially if you haven't then filled the drive and fully tested playback. If it wasn't for the successful restoration on Mac, I'd have immediately suspected a hard-drive problem).
Also, when its in an external enclosure you could try and format it properly in FAT32 (I'm not convinced you _can_ so format it while its still in the ipod, as I don't think a 5.5 gen ipod lets the computer see the true drive structure).