Windows Phone 8 Can't Connect to Exchange 2013

On an HTC 8x with Windows Phone 8 we were unable to connect to Exchange 2013 (but it connected to another exchange 2010 deployment just fine).  An iPhone was able to connect to both (just a bit of irony there for ya). After googling around a bit I found somebody suggest exporting the certificate with the private key, and lo and behold that actually worked.  Crazy that it's so difficult, but it did the trick.

We are using a Godaddy UCC cert on a brand new Exchange 2013 server.

The error on the HTC 8x:

You'll need a personal certificate to connect to mail.domain.com
last tried 2 minutes ago
error code: 85030027

Solution:
Export the cert with private key; I put it in a web accessible folder, and then went to that path from the phone, installed the cert, and it worked right away.

HTH