Creating HostedZone and Certificate though CloudFormation

Question

I am trying to create my HostedZone and Certificate though CloudFormation, i have the domain elsewhere but the Name Servers are pointing to AWS name servers.

It creates the HostedZone and the Certificate, but it stalls on the validation. With the config below it stalls on creating the validation DNS, and i can see that they CNAMEs are never created. With this status message Content of DNS Record is: {Name: _13ad388109470e17c9190af7767d2c30.example.com.,Type: CNAME,Value: _86b5f3453e00b7b75888d286f7420a02.dnzkjbsjxj.acm-validations.aws.}

I also tried using "HostedZoneID: !Ref HostedZone" but then it fails with the error: [The request contains an invalid set of changes for a resource record set 'CNAME _13ad388109470e17c9190af7767d2c30.example.com.'] (Service: AmazonRoute53; Status Code: 400; Error Code: InvalidChangeBatch; Request ID: eed1102a-c1a3-4dbd-b69b-20dc4ebf838a; Proxy: null)

Parameters:
  TopLevelDomain:
    Type: String
    Description: The top-level domain to use

Resources:

  HostedZone:
    Type: 'AWS::Route53::HostedZone'
    Properties:
      Name: !Sub '${TopLevelDomain}.'

  Certificate:
    Type: 'AWS::CertificateManager::Certificate'
    DependsOn: HostedZone
    Properties:
      DomainName: !Ref TopLevelDomain
      ValidationMethod: DNS
      SubjectAlternativeNames:
        - !Sub '*.${TopLevelDomain}'
        - !Sub '*.portal.${TopLevelDomain}'
        - !Sub '*.tenant.${TopLevelDomain}'
        - !Sub '*.owner.${TopLevelDomain}'
        - !Sub '*.vendor.${TopLevelDomain}'
      DomainValidationOptions:
        - DomainName: !Ref TopLevelDomain
          ValidationDomain: !Ref TopLevelDomain
        - DomainName: !Sub '*.${TopLevelDomain}'
          ValidationDomain: !Ref TopLevelDomain
        - DomainName: !Sub '*.portal.${TopLevelDomain}'
          ValidationDomain: !Ref TopLevelDomain
        - DomainName: !Sub '*.tenant.${TopLevelDomain}'
          ValidationDomain: !Ref TopLevelDomain
        - DomainName: !Sub '*.owner.${TopLevelDomain}'
          ValidationDomain: !Ref TopLevelDomain
        - DomainName: !Sub '*.vendor.${TopLevelDomain}'
          ValidationDomain: !Ref TopLevelDomain

  MxRecordSet:
    Type: 'AWS::Route53::RecordSet'
    DependsOn: HostedZone
    Properties:
      HostedZoneId: !Ref HostedZone
      Name: !Sub '${TopLevelDomain}.'
      Type: MX
      TTL: '300'
      ResourceRecords:
        - '1 aspmx.l.google.com'
        - '10 aspmx2.googlemail.com'
        - '10 aspmx3.googlemail.com'
        - '5 alt1.aspmx.l.google.com'
        - '5 alt2.aspmx.l.google.com'

Outputs:
  CertificateArn:
    Description: 'The ARN of the certificate'
    Value: !Ref Certificate
    Export:
      Name: CertificateArn

  HostedZoneId:
    Description: 'The ID of the Hosted Zone'
    Value: !Ref HostedZone
    Export:
      Name: HostedZoneId

With HostedZoneId instead:

Parameters:
  TopLevelDomain:
    Type: String
    Description: The top-level domain to use

Resources:

  HostedZone:
    Type: 'AWS::Route53::HostedZone'
    Properties:
      Name: !Sub '${TopLevelDomain}.'

  Certificate:
    Type: 'AWS::CertificateManager::Certificate'
    DependsOn: HostedZone
    Properties:
      DomainName: !Ref TopLevelDomain
      ValidationMethod: DNS
      SubjectAlternativeNames:
        - !Sub '*.${TopLevelDomain}'
        - !Sub '*.portal.${TopLevelDomain}'
        - !Sub '*.tenant.${TopLevelDomain}'
        - !Sub '*.owner.${TopLevelDomain}'
        - !Sub '*.vendor.${TopLevelDomain}'
      DomainValidationOptions:
        - DomainName: !Ref TopLevelDomain
          HostedZoneId: !Ref HostedZone
        - DomainName: !Sub '*.${TopLevelDomain}'
          HostedZoneId: !Ref HostedZone
        - DomainName: !Sub '*.portal.${TopLevelDomain}'
          HostedZoneId: !Ref HostedZone
        - DomainName: !Sub '*.tenant.${TopLevelDomain}'
          HostedZoneId: !Ref HostedZone
        - DomainName: !Sub '*.owner.${TopLevelDomain}'
          HostedZoneId: !Ref HostedZone
        - DomainName: !Sub '*.vendor.${TopLevelDomain}'
          HostedZoneId: !Ref HostedZone

  MxRecordSet:
    Type: 'AWS::Route53::RecordSet'
    DependsOn: HostedZone
    Properties:
      HostedZoneId: !Ref HostedZone
      Name: !Sub '${TopLevelDomain}.'
      Type: MX
      TTL: '300'
      ResourceRecords:
        - '1 aspmx.l.google.com'
        - '10 aspmx2.googlemail.com'
        - '10 aspmx3.googlemail.com'
        - '5 alt1.aspmx.l.google.com'
        - '5 alt2.aspmx.l.google.com'

Outputs:
  CertificateArn:
    Description: 'The ARN of the certificate'
    Value: !Ref Certificate
    Export:
      Name: CertificateArn

  HostedZoneId:
    Description: 'The ID of the Hosted Zone'
    Value: !Ref HostedZone
    Export:
      Name: HostedZoneId

I tried removing most of the subdomains and only have example.com and *.example.com, this cause the same issue. But if i have no alternative domains and only have exmaple.com it works.

  Certificate:
    Type: 'AWS::CertificateManager::Certificate'
    DependsOn: HostedZone
    Properties:
      DomainName: !Ref TopLevelDomain
      ValidationMethod: DNS
      DomainValidationOptions:
        - DomainName: !Ref TopLevelDomain
          HostedZoneId: !Ref HostedZone