It’s been a long and frustrating day trying to figure out why I’ve been receiving the error message in this post’s title when trying to connect my Droid 1 to my Exchange server. I’m running Exchange 2010 SP1 and Android 2.2. I’m running CyanogenMod 6.1 RC3 on my phone, but as far as I can tell, I’ve been affected by this problem ever since Froyo came out.
I was almost certain I had a certificate issue at first (based on all of the information I was able to find), but it appears it was actually just a problem with the ActiveSync policy on my Exchange server. To resolve the issue, I removed my device from my Exchange mailbox account, then deleted the default (only) ActiveSync policy on the server, then set my phone up with my Exchange account, and it worked fine.
See this thread for more details. Post 56 is what solved it for me.