Best way to format HFS+ to NTFS?

I recently got a Western Digital external HD: "My Book for Mac". Except I don't intend to use it for a Mac (the box says its Windows compatible with an initial format). Anyway, I have access to Linux (Ubuntu), Windows 7, and a Mac. I'm wondering which OS is best to use for formatting the drive. I would like it to be in NTFS format since I need it to work with both Linux and Windows (I do not need it to work with a Mac).

The hard drive is not recognized at all by Windows, so it seems I will not be able to format it there. I can format it to exFAT from the Mac. I assume then Windows would recognize it and I could reformat to NTFS. Is there any reason not do this? I read that Mac doesn't do a good job of converting to FAT.

In Ubuntu I tried to format from the "Disks" program, but it timed out--this program doesn't seem to be able to format anything (not to mention it didn't give me any options like NTFS, EXT, etc.). I started to follow this guide: http://ubuntuforums.org/showthread.php?t=267869 The following warning scared me from continuing: "WARNING: GPT (GUID Partition Table) detected on '/dev/sdc'! The util fdisk doesn't support GPT. Use GNU Parted."