You need to format it on a PC. Doing it through the Mac will not change the file structure (HFS+ for Mac iPods, FAT32 for Win iPods) - Windows cannot natively read HFS+ file structures.
To restore the iPod to it's factory settings follow
these instructions.
This will delete all the music on the iPod but you were going to sell it empty anyway, right?