Greetings fkrueger,
When this error is encountered it is because the CA certificate or intermediate CA certificate has not been installed on the Symantec Messaging Gateway to complete the certificate chain. The CA certificate or intermediate CA certificate must be installed prior to the installation of a certificate. These should be available from your certificate provider.
Please find below, documentation on how to install a CA certificate or intermediate CA certificate.
Error: "Cannot build a trusted certificate chain for the certificate. Please make sure that you have added all the necessary CA certificates."
http://www.symantec.com/docs/TECH90777