Ok, so I finally got it to work, although I must admit I'm still not entirely sure what the issue was. I did the following:
1). Download and burn
Gparted to a CD.
2). Go to Disk Management (right click computer->Manage).
3). Right click the box to the left of the volume and set partition style to GPT.
4). Right click on the volume->create new simple volume.
5). Create a new volume with the maximum size (~740GB).
6). Format the disk volume as NTFS (I set allocation unit size to 4kb, but am not sure whether this was necessary).
7). Put in the Gparted CD and reboot windows.
8). Follow the command line instructions to boot Gparted.
9). Load up the disk tool then select your volume from the dropdown menu in the top-right.
10). I saw the full disk space (3TB) split into a 740GB region allocated and the remainder unallocated.
11). Right click on the allocated region and click Grow / Shrink.
12). Drag the bar at the top so your volume covers the whole 3TB.
13). Click apply.
14). Reboot from Gparted, remove the disk and boot into Windows.
15). The disk was then 3TB in size in Windows.
