I recently went through an interesting experience of having to re-create the CA in a network and regenerating all of the keys for the servers. Which for the most part worked well except I had an issue with the BES server and it not being able to connect back to the mail server. This was somewhat expected, we had to re-generate the keys for the other hosts against the new CA for them to connect back. The BES was a little different, we did not have to do it’s keys be re-add the CA and the mail servers keys to it’s windows key store. Not the BES servers specific key store which through me for a loop for a minute or two.
Specifically you need to add the CA and the mail servers new certs in to the trusted root cert authority.