did you do a full restore on it? it sounds like you had a FAT formatted iPod and when you updated it to the new software you told it to reformat to an HFS iPod.
the solution...run the software restore from a PC and it will format it back to FAT. then hook it back to your mac and resync all your stuff