Exchange certificate error/setup

OK, I am pretty new to exchange, and I hate certificates.  Not a total newb but don't skip the obvious please.  Additionally, I am picking up this system from old admins that left on bad terms.

The core problem is this.  On setting up a new user on a new computer, I receive a certificate error.  I can skip it and it will run through, but my users freak out, and I do not want to teach them to ignore these warnings, so I need to get it fixed.


The Error is

The certificate is

From this, it appears that the Mailserver.domain.com is using a self signed cert, and is also SHA1.

The environment is like this

The Root CA does not have a website I can download the root cert from (broken?)
The Sub CA does and appears to be working

There are a bunch of certificates on all 3 exchange mail servers, most all are self signed I THINK  

Only listing the certs in the exchange MMC IIS console;
MailServer.domain.com
ex-mail1
exmail2

There ones listed in the web admin page are similar, only excluding the one that is expired.

There are so many, few to none match.  No rhyme or reason.  

I THINK I need to add a good cert from the Sub CA, and then remove the bad certs.  But this is a production box, and I am worried about removing certs that haven't expired, bad past experiences.


I guess I am asking for some guidance in cleaning up this mess.