You need to back up and obtain more information. Other answers have been assuming that you're using MBR, but your comment that you're using UEFI firmware raises the possibility that you're already using GPT. If this is the case, then the error message you received is a bug. You can check your partition table type in various ways, depending on the partitioning tool you're using. In Linux, one easy way is to type sudo parted -l and look for output like the following:
Partition Table: gpt
This output indicates a GPT disk. An MBR disk will specify msdos rather than gpt. Once you've determined your disk type, you can proceed without guesswork. Chances are you are using MBR and BIOS-mode booting of Windows, but it's best to be sure before doing anything radical.
Windows (including Windows 8, AFAIK) ties its boot mode (BIOS vs. EFI) to its partition table type (MBR to GPT). Thus, switching from MBR to GPT will necessitate converting Windows to boot in EFI mode rather than in BIOS mode. This adds complexity to the task -- too much to describe here, in fact. For more information, see this article. I don't recommend trying this unless you're desperate, although it really is the better solution in many ways.
It is sometimes possible to "fudge" things using MBR to get just under 4TiB out of it. To do this, you must assign everything above the 2TiB mark to one partition. In your case, if you're using MBR and the existing partition(s) consume up to the maximum point, you can shrink the final partition on the disk by a small amount (1MiB is the smallest that's practical in many new tools). You can then create the final partition such that it begins before the 2TiB mark and extends to the end of the disk (or for a size of 2TiB, if that's smaller). Note that if you want to use multiple partitions in Linux, you'll need to put all but the last of them entirely under the 2TiB mark, so you may need to shrink your final existing partition by significantly more than 1MiB. Also, be aware that this method is playing a bit "fast and loose." It's technically legal, given the way the MBR data structures are designed, but some OSes flake out with it. AFAIK, both Linux and recent versions of Windows work with it, but if you need to use the disk with something more exotic, it might behave strangely.
If it turns out you're already using EFI-mode booting and GPT, then the error message you received represents a bug. I'm not sure how you'd get around it, but shrinking the final existing partition, as in the MBR solution, might conceivably work. Beyond that, filing a bug report is in order.
