I get the same problem on my iPhone. it may be a 3.1 problem. An account I'd setup previously still works, but now I get the error you report on both my iPhone and on regular Mac OS X 10.6.1 if I try to setup a new Mail account on the same server. I let it default to IMAP, but SNMP doesn't work either.
This is suspiciously like an issue that occurred when they upgraded Mac OS X to Snow Leopard (10.6). It required a fix at my main ISP (Frontiernet) and Apple claimed they'd fixed it in Mac OS X 10.6.1.
I'm going to report the certificate error to Totalchoicehosting as my daughter is seeing exactly the same issue with her email. I'm also going to file a bug with Apple.
