Backups Started Failing - Mac Time Machine

Nothing has changed with my system. I’ve been backing up via Time Machine (Snow Leopard OS) for months now without an issue. All of a sudden I’ve started getting a message that there’s a network problem:

Time Machine Error

Make sure your computer and the backup disk are on the same network, and that the backup disk is turned on. Then try again to back up. The last successful back up was on 11/6 at 2:45AM.

In Finder, it shows that the MyBookLiveDuo is connected - I have access to the files stored there. However the MyBookLiveDuo-backup says Connection Failed.

I did a reboot of the drive and computer, but that didn’t help. I’ll do a reboot of those, plus my router, just to take that out of the equation. I’m not really sure where to start to troubleshoot this.

I went through the select disk process again - it’s back to backing up, however it’s like it’s the first time.