Apple, on Wednesday 9/9/09, released an update to iPhones OS. Apple is now enforcing a policy that is used to encrypt communications between Exchange 2007 mail servers and mobile devices, including the iPhone. Currently the issue seems to be only affecting users with the original iPhone and the iPhone 3G models (not the latest 3GS devices).
Exchange 2007 has a separate security policy for mobile clients, not present in Exchange 2003. Exchange 2003/iPhone connections are not affected by the 3.1 firmware update.
At this point the only available fix is to turn off the encryption requirement for mobile devices (to allow non-3GS iPhones to connect to the Exchange 2007 server). Affected users should also consider rolling back to the previous version of the iPhone OS, 3.01, rather than changing the Exchange server settings.
Hopefully Apple will have a better (more secure) fix shortly.