Time Machine stuck on "Waiting to Complete First Backup"

Dear fellows,
Yesterday I got my Ex2 Ultra, installed it, and everything went fine until I attempted to use it as a Time Machine backup. Now no matter what I do, it stays in “Waiting to Complete First Backup” and nothing happens. If I click “Backup Now” it enters into “Preparing Backup…” and after some time it goes back to “Waiting to Complete First Backup”. Reboots of all devices involved are not helping. I tried every step I could find on the internet but still nothing. Can you help me with this issue?