Reconfigure Microsoft Exchange Server to Use a Fully Qualified Domain Name

Hi.
I have 2 clients running exchange server 2010.  
I needed to upgrade their exchange ssl certificates.  I was told when I was renewing them that certs can no longer contain the local name of the exchange server.  
So I renewed the certificates with only the outside domain name mail.yourcompany.com
I ran these commands in the exchange shell:

To change the Autodiscover URL, type the following command, and then press Enter:
    Set-ClientAccessServer -Identity main-fs -AutodiscoverServiceInternalUri https://mail.mycompany.com/autodiscover/autodiscover.xml

    To change the InternalUrl attribute of the EWS, type the following command, and then press Enter:
    Set-WebServicesVirtualDirectory -Identity "main-fs\EWS (Default Web Site)" -InternalUrl https://mail.mycompany.com/ews/exchange.asmx

    To change the InternalUrl attribute for Web-based Offline Address Book distribution, type the following command, and then press Enter:
    Set-OABVirtualDirectory -Identity "main-fs\oab (Default Web Site)" -InternalUrl https://mail.mycompany.com/oab
   
    To recycle the application pools, open IIS Manager.
    Expand the local computer, and then expand Application Pools.
    Right-click MSExchangeAutodiscoverAppPool, and then click Recycle.

Today the users are complaining about a cert popup in their local outlook clients.  

What do I need to do to fix this?

Wes