Time Machine automatic backups fail, manual backups succeed
Not a real answer, more a workaround to have your backups automatically despite this bug. That worked for me (see this answer of my own question).

Open a command line and say tmutil destinationinfo. Copy the ID you see in the ID line (a long suite of alphanumerical characters and -'s).

Now type tmutil startbackup -d TheID replacing TheID by the ID you just noted before (so something like tmutil startbackup -d 11326F32-D5BA-4FE8-83FB-E9CBD8F6FF2D but with an other ID). Open Time Machine Preferences and check if the backup is running. You may have to wait a few seconds before you see anything.

If that works, you can add it to your crontab so it is automatically run manually every hour (sounds contradictory?). Type crontab -e on the command line to edit your cron jobs, and add the following line in it:

0 * * * * tmutil startbackup -d TheID


again replacing TheID by the ID of your backup. Next hour check if anything is happening. You can replace the leading 0 by the minute you want it to be run.