On our Azure AD sync server all services were running that should be. I found a service called:
"Microsoft Online Services Sign-in Assistant"
Description - "Enables authentication to online Microsoft services"
I restarted this service and then was able to login straight away online again.
I hope this helps anyone else caught by this error.