We had the same problem. I just asked the Certificate Authority to add a “Subject Alternative Name” that matches the internal name to a single certificate. This is through verisign. not sure if other CA will do the same.
email.company.net – Subject Name
another.company.net – Subject Alternative Name
Take a look at my <a href=”http://itknowledgeexchange.techtarget.com/it-trenches/certificates-who-do-you-trust/”>blog entry</a> about certificates and Exchange. This will help you understand why this is happening. The clients need to have a path to or trust the root certificate authority.