iCloud Backup don't work for iOS Microsoft Authenticator App

Question

Good day,

I switched over to iOS from Android a few months ago (6+) but never been able to use MS Authenticator as I can't get iCloud enabled. I have read lots of forums about enabling iCloud for the app via settings, re-installing, etc, but non of these worked. In the mean time I also upgrade my iPhone, thus tried it again on a fresh iOS, still the same issue.

So what I did was to open MS Auth app on my iPhone, then go to Settings and clicking the check to enable iCloud Backup. Then I am asked to login, which I do and everything seems to go fine, def the correct creds. I then get redirected back to the app, it shows something is happening and then a little box pops up saying:

Something went wrong. Please report an issues using the "Send feedback" option and try again later.

So I have tried sending feedback a few times with no luck or responses from MS. If anyone's interested, here is my most recent incident nr: VUX8BFEP

I have also read through tons of forums on checking your setting under icloud, enabling it for Authenticator. Tried that as well. If I use another MS account it works, just don't work with my own MS account. I have also tried disabling two factor auth, that also did not work.

Hope someone out there can help! Thanks in advance.