There seems to be many people having issues with s self signed SSL certificates on Exchange. The phone requires you to load the certificate and "trust" it before you can connect. It doesn't allow for you to "trust" it inline with the EAS setup (ala Windows Mobile and iPhone). If you get past that, and you are running a standard SBS sever which by default creates a self signed cert with CNs for the private AD host name, the public dns host name and some SBS specific websites (companyweb and others). The pre supports multiple CN certificates, but it seems from some early research I did with a friend who just picked one up, that it uses the 1st CN to create the SSL connection (or verify the root ca) instead of the server url the user entered in the setup. Since many small shops don't use their public domain name as their AD domain name there seem to be many people having an issue.
Also, the error message it provides is not very helpful and is generic "SSL certificate error. Is the date and time correct"
Thankfully my friend's company happened to own the domain they used for the internal AD as well and since he is the admin he just added in the DNS records for it. It then worked as designed.