Adding a Time Machine destination fails with OSStatus error 17
Digging through the console I found this telling error:

NetAuthSysAgent already_mounted: share &lt;TIMEMACHINE&gt; already mounted


TIMEMACHINE is my share name in this case. As the error suggests, Time Machine is trying to mount the share again which it can't do because it's mounted already. But wait! If I disconnect from the share will leave my list! 

Here's where some weird UI trickery comes in:


Connect to the share using Finder
Open Time Machine preferences, click 'Select Disk', and then double click the disk at your desired address (in my case I wanted my FQDN). You should now be at the authentication prompt.
With the authentication prompt still open, go back to Finder and eject the share
Sign in to the waiting prompt


and the disk should be added! I've never had this issue before but it's come up on High Sierra which as it turns out has some really bad AFP/SMB bugs.