OK, what happens is that Mac can read and write to Windows (FAT32) formatted disks. However Windows cannot read or write to Mac (HFS) formated disks. When you buy a Nano it is originally formatted to Windows and loading it onto your Mac will format it to HFS.
This now means that your Nano is unrecognisable to the PC so you did a full reformat and it is now Windows formatted again.
It should however now work on both Mac and PC but you will have to use a PC to apply any firmware updates. My 3G iPod is formatted to Windows and I have set it up to manually manage music. This means i can use my iPod on both PC and Mac without running the risk of deleting all the music on it.
A Windows formatted Nano should work with Mac, if it doesn't, then Apple have implemented some sort of new deal where you can only use the Nano on one platform - sounds a bit silly so i don't think they have.
Keep it formatted in Windows and just plug it into the Mac, don't load anything, don't use the disk, just plug it into the Mac and see what happens.