None of these worked for me, have tried to solve for a few months here and there. I've seen a lot of posts, but most folks say the workarounds don't work for them. Here's what worked for me.
Open airport utility (i was using v6.1 (610.31))
Click on the Base Station tab
Click on the + button to add under Back to my MAC
Enter your apple ID and PW
Click on sign in
Close the airport utility
Click on time machine in the menu bar
Select the Run a Backup Now...
My backup started working after these steps...
The forum guru Pondini's advice did not work for me, I suspect it's out of date as the UI did not match the current UI version for airport utility, so options like trying to disconnect users were not there anymore! 😉
Hope this helps someone, I finally had to figure this out on my own... Good Luck!