Outlook Anywhere Exchange 2010

I am trying to configure Outlook Anywhere on an Exchange 2010 server and having some difficulty.  I have enabled Outlook Anywhere in the EMC and given exchange.mydomain.com as the external host name.  This exchange server has bene reachable via OWA and Activesync for years now so the proper DNS records and firewall settings are in place for that.  I created a DNS record for autodiscover.mydomain.com which points to the same IP as my exchange.mydomain.com DNS record as they are the same server.

When I try to configure my Outlook to conenct, I get an message "The connection to Microsoft Exchange in unavailable.  Outlook must be online and connected to complete the action".  I know I am missing something in the steps to setup Outlook Anywhere, but I am not certain what.

I read somewhere that I needed a certificate for autodiscover.mydomain.com but I am not sure how I could use two certs, exchange.mydomain.com and autodiscover.mydomain.com

I appreciate any help.