I had the same problem setting up a new iMac to backup to a NAS. The old iMac (same OS version) worked fine so I was perplexed.
I found a lot of nonsense on the internet, but eventually the following worked for me. I went into Keychain Access and found the relevant entry in the System keychain. I then edited this entry and changed the URL (Where: field) so that it exactly matched the error message. The point is that in the Keychain, the URL appeared with a space, but the error message has the space replaced with %20. So, replace each with %20 and it may work for you too.
I Think what is happening is the Time Machine widget is encoding the remote drive location as a URL at some point in a way that the Keychain is being accessed inconsistently. I noticed that in the login Keychain, entries were appearing with no username or password set, which presumably happens when the error occurs.
I'd be interested to know if this works for anyone else, as it's a very frustrating problem and if the fix is as easy as this, then I suspect the bug will be straightforward for Apple to fix too.