You get a new removable hard drive that is 3TB. Your Windows machine sees it fine, formats it fine, everything is good to go. You point you backup job to it only to discover that it fails with totally cryptic messages logged in the event viewer

This article describes the problem and resolution very well, no reason for me to re-iterate it. How it worked for me:

1. I did have a Western Digital removable hard drive and the utility supplied by Western Digital indeed formatted it in a way where it emulates old 512 sector. When researching the issue I also saw that Seagate supposedly has a similar utility, so may some other drive manufacturers.

2. Then you have to add the drive back to the list of backup targets using the wbadmin command-line utility. It says that it will format the drive to claim it for exclusive backup use, but apparently does not. Once it claimed the drive for itself I went to disk management, assigned that drive a letter and ran fsutil fsinfo ntfsinfo x: and it still showed 512. So then I removed the drive letter, scheduled backups work.