note that the problem may also be on the Client side, especially with IE/Edge and Chrome since AFAIK they both use SChannel to verify the certificate chain. The client may have buffered the Let’s Encrypt X1 certificate, and they might first use the buffered certificates instead of the intermediate sent by the server to verify the chain, and since IIS (wich also uses SChannel) is able to build the wrong chain with the X1 instead of X3 certificate, the same case might happen on the client side with IE and Chrome even if the server sends the correct X3 intermediate (provided that the user previously visited a website on that computer which uses the old X1 intermediate).
For example, I once had a problem with an StartSSL certificate where the intermediate certificate used SHA-1 and expired after Jan 2016 (Chrome shows a warning in that case). Later, StartSSL published a new Intermediate that used SHA-256, but you could use that new intermediate with the same leaf certificate you already had. So, I removed the old SHA-1 intermediate and added the new SHA-256 intermediate on the server, and according to SSLLabs, the server sent the correct SHA-256 intermediate. However, on most PCs (where I previously visited that page) browsers like IE and Chrome still showed the SHA-1 intermediate with the warning, whereas on a freshly installed Windows VM they showed the new SHA-256 intermediate.
Note that this is only speculation, I have not yet tried to install a new Let’s Encrypt certificate with the X3 intermediate on one of my servers.