So this is basically how I resolved my issue.
I did a repair on the cert.
When I tried to install the cert via the EAC, I saw what I mentioned in my original question.
So I tried to install via the management shell. Then I saw an error that said the private key was missing.
Then after some reading on line I saw where some others experienced the exact same thing and what they suggested was to do a repair on the cert.
certutil -repairstore my "Serial number of cert"
After I did the repair, I did an enable on the cert:
Enable-ExchangeCertificate -Server ‘EXCHANGESERVER’ -Services ‘IMAP, POP, IIS, SMTP’ -Thumbprint "Actual thumbprint of new cert"
That did it. New cert was installed, enabled and working.
Done.