Microsoft Authenticator lost accounts

Hi, I have recently updated my iPhone X from iOS 10 to iOS 11.3.1 and during the update, I lost all my account codes in the Microsoft Authenticator app, I have tried the restore feature it has as I did have it backed up with my iCloud account but it says there is no data to restore from, yet if I goto Settings -> Apple ID -> iCloud -> iCloud Backup I can see a entry for the app, so it looks like the data is backed up but the app for some reason can not access it / restore using it.