Sounds like this issue, which is due to a misconfigured IPv6 interface. Essentially what is happening is that the client attempts to connect to the ACME server via IPv6, then times out and retries via IPv4 (which works).
Check the IPv6 configuration on your server or disable it completely. You can use something like ping6 acme-v01.api.letsencrypt.org to test connectivity.