Fail to register a new domain

I checked the domain is available

How did you do this, was it in Route 53 and did that come back with a water-tight this domain is available statement? Sometimes Route 53 won't hear back from the domain authority for that domain in time, and so Route 53 gives a reply like The TLD registry didn't respond in the expected amount of time but it will still to try and proceed to register for you. If it turns out the domain is already registered to somebody else it will fail further down the line.

Which top-level domain are you trying to register, is it .com or .net or a country-level, etc.? And does it exist on this list? https://docs.aws.amazon.com/Route53/latest/DeveloperGuide/registrar-tld-list.html

Sometimes even TLDs on this list can be refused, as a random example a two-letter domain name under the .me TLD will be refused https://docs.aws.amazon.com/Route53/latest/DeveloperGuide/me.html

Domain.me, the registry for .me domains, considers two-letter domain names and some longer domain names to be premium domain names. You can't register premium .me domains with or transfer them to Route 53.

You're probably not using .me I'm just giving it as an example, but it's worth checking there aren't any similar restrictions with the domain you are trying to register.

You can always raise a support call with AWS about this. Even if you're on a Basic Support plan (which would preclude you from raising a support call most of the time) you can still do so under Account and Billing -> Service: Billing -> Category: Domain Registration Issue

https://docs.aws.amazon.com/Route53/latest/DeveloperGuide/domain-contact-support.html