It appears the release of iOS 5 has caused some issues with Exchange accounts and ActiveSync due to insufficient secruity requirements on iOS 5. The error occurs when trying to add an account as an Exchange on the Mail.app (not Gmail) – the error looks like this:
This release has a known compatibility issue with Exchange ActiveSync if you have enabled “Require storage card encryption” in your Exchange ActiveSync mailbox policy. This setting specifies whether the storage card must be encrypted and for now at least, iOS 5 on the iPhone and iPad currently do not support this feature.
A list of EAS policies can be found here: http://technet.microsoft.com/en-us/library/bb123484.aspx
Unfortunately the only fix currently is to not update to iOS 5. Or if you are lucky enough to be the Administrator of that Exchange account then configure a new EAS policy which would not require “Require storage card encryption” and add the user to it, then uncheck “Require storage card encryption” from the EAS policy.
Hopefully this feature will be added in Beta 2 sometime in August and ActiveSync and iOS can play nice again!