For the last few months, TimeMachine has been failing for me between my Macs and a QNAP TS-659 NAS I have. The NAS is running firmware 4.0.3, and I would consistently get the error “Cannot connect” when trying to connect. I was able to work around this with the following command run manually:
sudo tmutil setdestination -ap afp://TimeMachine@192.168.64.38/TMBackup
Running that in a terminal window allowed me to then use the GUI to select that disk for backups and things started rolling again. In the above, make sure to replace “192.168.64.38″ with your IP or hostname of the QNAP. It will ask you for your password when you run the command. I found all of this on the forum thread here for reference.