There is some confusion about what this error code means. It can often be related to SSL certificate issues, which may have been part of my problem. I found this page very helpful to debug the SSL issues: http://kb.palm.com/wps/portal/kb/common/article/16733_en.html
Once I had that working (I did have to change the server name to match our certificate) I was still having issues, and I came across this post: http://episteme.arstechnica.com/eve/forums/a/tpc/f/579009962631/m/417009683931 that suggested the issue was the ActiveSync security policy. I tracked down our IT guy and cajoled him into testing out removing the policy, since ours didn't really do anything anyway. It worked! The odd thing is that the old domain seemed to have a policy as well but something must be different.
So apparently the Treo (Versamail 3.5.5) doesn't support ActiveSync with security policies. Ya, ya, time to upgrade to a real phone...
