My mail server runs Exchange 2007. I had to run the i780Patch that I found on the following thread to get it working. I think it may have something to do with the way my administrator enforces policies on mobile devices.

http://forum.xda-developers.com/showthread.php?t=485091