I had this same issue which was caused by the server using a self signed ssl certificate.
You can add an exchange account using a self signed ssl certificate to the Windows 8 Mail app. There is a lot of information on the internet indicating the contrary, however you CAN do it.
It requires installing the certificate using MMC (not cermgr) to [Console Root\Certificates (Local Computer)\Trusted Root Certification Authorities\Certificates].
- You must download the certificate to your Windows 8 device. If you have access to Outlook Web Access you can browse that website, click the certificate in the browser and save as a p7b file.
- From the desktop run MMC.exe
- Choose File->Add/Remove Snap-in...
- Choose Certificates, then click the Add button, and OK.
- Navigate to [Console Root\Certificates (Local Computer)\Trusted Root Certification Authorities\Certificates].
- Right click the "Certificates" folder, select All Tasks->Import...
- Choose "Local Machine", Next.
- Browse to the certificate file you saved on your device and click Next.
You might be able to install the certificate to a different folder however I have not tested that.
You can probably do the same thing by double clicking (opening) the p7b file, right clicking the certificate and selecting "Install Certificate...", then installing into Local Machine.... Although I have not tested that.
Once you have done this you will be able to add your Exchange account to Main/People/Calendar.
I have tested this on a Windows RT device and it does work.
Update: There are a couple other ways to install the certificate so if you are familiar with those you can choose the method you are comfortable with.
Also if you have a failover Exchange site with a self signed certificate, be sure to install the certificate from that server as well.