I am having the same problem described here: http://www.experts-exchange.com/Security/Encryption/Q_23339846.html
and have followed the solution to generate and enable a new certificate.
Yet, when I connect to the Exchange Server 2007 with Outlook 2007 I am still warned of the expired certificate and using the examine certificate feature shows me the same thumbprint of the certificate I thought I just renewed.
I was not sure if generating a new certificate required a server reboot, so I tried it anyway. Still have same error message.
I can see the new certificate in the MMC Certificates snap-in under Certificates (Local Computer) \ Personal \ Certificates. In fact, there are 4 and the get-exchangecertificate command returns their Thumbprints when I run it.