After many hours of work, I was able to SOLVE it on my machine.
I was having this problem (TM error 112) on one upgraded Big Sur machine, while others are backing up fine to Time Machine folders on Synology NAS.
After doing many things (several times), I was able to solve this.
1) Followed these Synology Instructions to make sure it's not Key corruption issue: https://www.synology.com/en-global/knowledgebase/DSM/tutorial/Backup/What_should_I_do_to_fix_the_problem_when_connecting_to_Synology_NAS_using_Time_Machine
2) Deleted Time Machine folder on NAS.
3) Deleted old user and setup a new Time Machine User on NAS.
4) Turned off Sophos Home Anti-Virus
All of that did not allow me to go further than creating a sparsbundle on NAS, with TM Preparing Backup, but then fail in ability to write files to the the NAS sparsbundle.
What finally solved it was:
5) Uninstalling Sophos by downloading Sophos removal tool. https://support.home.sophos.com/hc/en-us/articles/115005499786-Uninstalling-Sophos-Home-on-Mac-computers
Good Luck!