In Disk Utility, have you selected the Erase "tab"? This is the one that will let you reformat the drive. Try this and report back if it will let you.
What does worry me about what you seeing is that the drive doesn't appear to have any partitions on it - either a completely fresh drive or it has a corrupted partition table. This is why Windows doesn't see it - no partitions.
You may need to get something like PartitionMagic to format this thing, or use a Linux distro to do the same thing via QtParted.
I have had this happen to me once before. The Mac would successfully format and use the drive as is, without any entries in the partition table, but the Windows box was too stupid and couldn't see it. I eventually had to haul out a Linux distro (in this case SuSE Linux, and its YaST Partitioner) to reformat and rebuild the partition table.
This may be tough - good luck!