"Failed to create account. Please try again later" on my Sprint HTC Hero meant we had just moved to an Exchange 2010 server and I was using Android 2.1.
The solution was to go to HTC's web site and download HTC SYNC UPDATE FOR HERO (SPRINT) (2.0.40) | 06.16.2010 (since there aren't 16 months in the year, this must be 16 June). I connected my Hero to my PC at work using a standard USB cable and synchronized. It only does contacts and calendar. However, after that, the mail came through.
There were many other things I tried thrashing about to get it working and may or may not be necessary.
SSL does need to have the checkmark.
My belief is that this transferred a certificate to the phone which allowed the Exchange server to trust the phone, but I can't be certain.
If you're getting authentication errors, try the manual setup. If it still happens, one or more of the entries are not what they need to be. For me, it was that my email address is
firstname.lastname@company.com but my Windows log in name is my last name and first initial run together.