Licensed users are unable to access Bookings: Getting "Ask Your Admin"

We are using 11 Bookings calendars for an internal project, few users have started receiving the "Ask Your Admin" instead of taking them to the Bookings.

I have removed and re-applied the FullAccess and SendAs access using PowerShell. The license for MS Bookings was turned off and turned on. The licensing hasn't changed, they have always been on E3.

I have raised a case with Microsoft, but its taking ages to get some one to respond.

Any thoughts?