I had this problem, too, with Windows 7, trying to use Windows Backup to two new Western Digitial 3TB drives, pre-formatted with NTFS for Windows. It's very frustrating because each attempt takes many hours before the error occurs so you don't know until it succeeds whether it will.
I found what worked for me here:
http://wdc.custhelp.com/app/answers/detail/a_id/6618/
You can download WD Quick Formatter from that site. However, don't follow the instructions on that page for formatting a HD under Windows 7, because it tells you how to use MS Disk Management, which will make a 2TB partition and not recognize the remainder of the drive. You must use WD Quick Formatter as described here:
http://wdc.custhelp.com/app/answers/detail/search/1/a_id/3868
Good luck!
[I think it's unconscionable that MS hasn't fixed this with their built-in tools.]