FileVault is blocking the TimeMachine backup process

What does it say for filevault?

>System Preferences>Security & Privacy>FileVault

If it is E/D then you will have to wait.

If neither than there does seem to be some associated bug, did you reboot an try again?

Go into macOS Recovery (turn on your iMac and immediately press and hold the Command (⌘) key and the letter R on your keyboard until the Apple logo or spinning globe appears on your screen, then let go of the keys). Wait for the macOS Utilities window to appear on your screen, then choose Disk Utility, then press Continue and run First Aid on the Startup Volume, which is most likely your Macintosh HD. After First Aid repairs it or says that it's successfully completed the check on your Macintosh HD (with a white checkmark and an OK on a green background), shut down your iMac. Boot up your iMac normally, plug in your External HD for Time Machine backups to your iMac, and now you should be able to immediately begin backups on Time Machine. Please note: The preparing backup sequence on Time Machine will initially take awhile (like maybe 45 minutes or more) before Time Machine begins backing up.

Be aware that you can get quite a number of backups done on multiple backup disks for several days, before you may have to do it again (the procedure isn't too time-consuming anyway), but at least it's a quick fix to that devilish red circle with the "little white i" inside of it on the Time Machine window.   

Did the information button disappear? So there was no notification anymore and the backup runs okay on manually again?

"Time Machine did not back up because FileVault was encrypting or decrypting a disk. Backups will resume once FileVault finishes."

I'm sorry the procedure didn't work for you. Try this then → Run First Aid on your external HD for both the physical disk and the physical volume in Disk Utility located in your mac's Applications folder, in case there are any bad sectors on them that need repairing and to verify the disk and volume — that may take a long time depending on the amount of backups on the drive. Then try making a backup.

If that isn't enough, try this → go into macOS Recovery, when you get to the macOS Utilities window, choose Reinstall macOS and press Continue and follow the instructions (you'll most likely want to select the Macintosh HD as the disk for the reinstallation). Shut down your mac, connect your external HD to your mac, then reboot your mac normally. Reinstalling the operating system takes hours, but that may work.

Hi I had this problem since Feb 2019 after Mojave update and this solved it.

(Back up anything super important to cloud or another drive manually)

Go to your Sparsebundle on external hard drive - you might have several (This might take ages, mine took 4 days to remove all 474GB content as TImemachine had tried to save 4 separate backups - be patient) RIght click and click showpackage contents.

A file called bands will be there.

Click Bands and wait so all folders show - there are over 110 folders containing over 8000 files. Select all and then delete immediately "Option + Command + Delete." This might take 20 hours as mine did. Do this for each bundle. If there is a token file delete that after. Once there is no trace of any back up on the external hard drive click time machine and select new disk. "select ENCYPT " A new back up will start . The first back up was created in a few hours

Is there a bug fix?

No, this did not work.... ;(