"It's not you, it's us" with Okta as IdP for AWS SSO

After trying to access AWS account via Okta, users are getting the "It's not you, it's us We couldn't complete your request right now. Please try again later." message. It's been occurring for more than a week. Integration was configured by following this guide: https://docs.aws.amazon.com/singlesignon/latest/userguide/okta-idp.html and previously worked fine with another AWS account.