@_az, a new suggestion for something else to check: with DNS-01 _acme-challenge.example.com doesn't exist but _acme-challenge.example.com.example.com does. E.g.
I realize that letsdebug doesn't reject DNS-01 configurations where the _acme-challenge TXT record hasn't been created yet, but nonetheless it could generate a useful warning when the corresponding record with a duplicated base domain name does exist!