Hi,
I'd restart your Edge server if you haven't already done so, and check that you have not accidentally assigned the certificate to only specific Edge services and Sneff_Gabor suggested.
Could you confirm that you used the Lync Certificate Wizard to generate the CSR's for these cert's rather than generating them through some other means?
If you haven't already done so, import and assign the certificates for a second time post Edge restart to see if this makes a difference.
If you're using a third party public certificate for you external Edge services, make sure that you have any required root and intermediate certificates in place for a valid chain. You can check this by viewing the certificate details and looking
at the 'certification path' tab to ensure your public certificate is trusted.
If you don't have any luck, create a new CSR for your External Edge services and generate a certificate from your internal CA rather than through a public CA and assign that. This will tell you if it's the external certificate that's causing an upset.
Can you confirm the 'public key' and 'signature algorithm' on the details tab of both certificates?
Kind regards
Ben