Hello @netamity ,
You don’t happen to be using Cloudflare DNS provider?
This same problem was reported by another user with this provider and the solution can be seen here AWS Cloudformation domain issue
If you’re not using Cloudflare, tell me and we’ll keep investigating.
Regards