I got this error today when trying to partition a Western Digital My Passport 4TB:

Volume erase failed: Media kit reports not enough space on device

Nothing I could do inside Disk Utility worked. Thanks to some kind soul on Reddit, here is how I solved the issue from the command line:

$ diskutil list
$ diskutil unmountDisk force disk2  #replace disk2 with your disk number

and then write zeros to the boot sector:
$ sudo dd if=/dev/zero of=/dev/disk2 bs=1024 count=1024

Attempt to partition it again:
$ diskutil partitionDisk disk2 GPT JHFS+ "My External HD" 0g