Apple has posted a remedy for;
The account "______________" requires encryption which is not supported on this iPhone.
the error some iPhones and iPods getting after upgrading to iPhone OS 3.1. Get an iPhone 3GS! or ask your Exchange administrator to relax the policies.
"iPhone OS (beginning with the iPhone OS 3.1 update) can enforce the Exchange ActiveSync mailbox policy requiring encryption on the device. If your Exchange Server administrator has selected this option, only devices that support device-level encryption are allowed to sync Mail, Contacts, and Calendars.
To reestablish syncing, have your Exchange Server administrator change the mailbox policy to no longer require device encryption.
Additional InformationNote that iPhone 3GS supports device encryption.
There you go!
Apple's Support Document