I had some of the same issues describe above. I have an iPhone 3GS running iOS4, it worked fine on Exchange 2003, but after migrating to Exchange 2010, it suddenly stopped working.
I am truly sorry to say, that my issue was not caused by Apple, but a new security settings set by default on Exchange 2010. See this forum thread: http://social.technet.microsoft.com/Forums/en-ZA/exchange2010/thread/37a1cb86-d4e3-4851-b41b-f8e42997dd6c
I had the same symptoms. The event (1053) was present on our CAS, that Exchange ActiveSync doesn’t have sufficient permissions to create the user object. I am member of Domain Admins, and thereby member of a protected group.
I did as described in the forum thread, Included inheritable permissions from the object’s parent, on my own user object. And after deleting the exchange account on my iPhone and setting it up again it all worked fine again.