That’s interesting, because CACert.org has never been trusted by default in browsers, so the old server would have had the same “certificate not valid” problem. I’m guessing everyone had already set up security exceptions for it, so it seemed to just work. Alternately, it’s possible but unlikely that everyone at your company manually installed CACert.org’s trust root on their computers.
That means that by getting a publicly trusted Let’s Encrypt certificate you’ll be going above and beyond what was in place before. So don’t feel too bad if it’s hard, and make sure you get credit for the improvement.