What type of certificate are you using and do you have all of the possible server names in the certificate. Keep in mind that wildcard certs are not supported in the exchange scenario.
http://technet.microsoft.com/en-us/library/bb851505(EXCHG.80).aspx
