Hi there, I have seen that many times!
The solution is to open the local certificate store on the Exchange server for the local computer.
Type at the RUN Menu:
certlm.msc
Find the OLD cert that you want to remove under the "Personal" container and delete it from there by right-clicking on it and choosing delete. Make sure you choose the old one ( verify by date and thumbprint.
After that , do an IIRESET to ensure its removed and you are good.