Whether the DNS works properly in a browser isn’t a good test for whether it will work with Let’s Encrypt, because Let’s Encrypt verifies the correctness of DNS records in detail much more stringently than browsers do. We’ve had many cases before where sites worked fine in browsers but had various DNS configuration glitches that interfered with issuing certificates.
A common example (which isn’t necessarily related to your case) is DNSSEC misconfigurations and mismatches. Browsers don’t necessarily enforce DNSSEC checks at all—but Let’s Encrypt does. So someone with a DNSSEC configuration problem might well be able to browse to the site yet still not get a certificate.
I was trying to find a good analogy for this difference, and I’ve found one that I kind of like but that’s obviously not totally exact. This is that an immigration agent at a border checkpoint is likely to apply more scrutiny to your identity documents than a bouncer in a nightclub or a convenience store clerk does. Therefore, the fact that a convenience store clerk accepted an ID for purposes of tobacco sales or something doesn’t guarantee that a border agent will accept the same document. Indeed, they’re likely to disagree about whether the document should be rejected if it’s expired recently.
Similarly, Let’s Encrypt is trying to perform a validation in order to vouch for the correctness of something to the general public, and so its interpretation of the technical details is much more stringent than a browser’s might be.
Do you have tech support available from the hosting provider? They would probably be in a position to fix the DNS configuration problems once they’ve understood the details.