Apple Support has posted the first of (no doubt) many issues with the brand new iPhone OS 3.1:
When using a Microsoft Exchange account on an iPhone or iPod touch, the following error message may appear:
The account "______________" requires encryption which is not supported on this iPhone.
Turns out 3.1 can enforce the Exchange ActiveSync mailbox policy requiring encryption on the device. When that option is turned on by the server admin, only devices that support device-level encryption are allowed to sync Mail, Contacts, and Calendars.
The only workaround is to have your Exchange Server administrator change the mailbox policy to no longer require device encryption.