iPhone 3.1 apparently fixes a bug that didn't properly enforce Microsoft Exchange 2007 SP1 encryption policies, and that looks to be causing problems for users of the iPhone 3G and iPhone 2G (and likely first and second gen iPod touch users as well).
While the iPhone 3GS supports Exchange encryption and is thus unaffected, the previous generation devices reportedly do not, leading to the error shown above.
Outside buying an iPhone 3GS or getting your Exchange Admin to turn off the encryption requirement (good luck with that!) we're not sure if there's a fix for this fix yet.
If you've run into the problem, however, drop us a note in the comments.