Time Machine on my Mac started giving the "The backup volume could not be found" error when backing up. To make matters worse, it never gave a big "Backups are NOT HAPPENING" type of error dialog.

It turns out that I had disabled the built-in Ethernet, when I was testing a USB-Ethernet adapter. Time Machine apparently relies on the MAC address of the built-in Ethernet. Re-enabling the built-in Ethernet corrected the problem.

I had heard that some people had trouble with Time Machine on a Western Digital (WD) MyBook External drive, so I was worried that it wouldn't work on my 1TB WD MyBook.  It worked fine, once I re-enabled the Ethernet.

The connection between a USB disk drive and an Ethernet address and Time Machine certainly violates the "principle of least surprise."