If you use a private certificate authority, users will receive the certificate error you describe. This is due to the fact that unless the client computers are part of the domain where the enterprise CA is located and they have that authority in their list of trusted root certificate providers, the private CA is “untrusted”. To remove this OWA certificate error, you should purchase a certificate from a trusted third-party such as Thawte, GeoTrust or Verisign. See my blog entry for additional discussion on this topic. Certificates – who do YOU trust?</a>
In the IT trenches? So am I – read my IT-Trenches blog.
Even if you have any Enterprise Root Certificate Server installed on your network, you can install that Third Party Certificate to Server and point your clients to Trust the certificate to that Server. This would resolve the issue