I have seen that problem on a number of occasions. The following technique fixed it.
Open Time Machine Preferences and de-select the Back Up Automatically checkbox. Make sure no backups are in progress, otherwise you'll have to wait for it to finish or terminate.
Then, click the "Select Disk..." button, select the backup disk, then Remove Disk, then Stop Using This Disk.
If you designated more than one backup destination, the "Select Disk..." button is replaced by an "Add or Remove Backup Disk..." option. You have to scroll through the list of backup disks for that option to become visible.
This will not affect any existing backups.
Then, Select Disk... again. Re-select the same one under Available Disks, then Use Disk. If the backup is on a network (TC or AEBS), you will be prompted for the password you provided for that disk in AirPort Utility.
"Waiting to complete first backup" will appear, which means it won't do anything until the next scheduled backup. That does not mean it needs to create a completely new backup, as if it's creating a brand new one. Your existing backups will still be available.
If you don't want to wait that long, select Back Up Now.
A Notification may appear if your source volume is encrypted and the backup volume is not. That's normal.
Re-select Back Up Automatically.
The "Preparing Backup..." status message will remain for a long time. Eventually, "Backing up xxx of yyy" will appear, but those values will not be accurate, nor will the "Estimated time remaining" in Time Machine's Preferences. Just ignore it. Despite those indications the backup it creates will be the usual, incremental backup; not a completely new one. It may take a few hours even if your Mac is not allowed to sleep. Time Machine will also pause or become slow if you use your Mac for tasks it considers a higher priority, which is new in Sierra.
There is one report on this site for which the above did not resolve the problem, but reinstalling Sierra did: How to reinstall macOS - Apple Support. Follow "If you're reinstalling for other reasons" and skip Step 2 (because you are not going to be erasing that Mac's internal storage). Reinstalling macOS in this manner does not alter any User Accounts or their data.
If all else fails Contact Support. You will certainly need to speak to a senior level support specialist. Be patient, because Apple's first tier support will ask a bunch of fundamental questions to eliminate all the obvious causes, after which they will most likely have you perform everything you already did all over again.