Have you tried using the likewise software (http://www.likewise.com/index.php ) to connect your linux to the MS domain – that might actually solve some of the issues evolution has in connecting to the exchange server ?

since it will work as a “native” AD client , some of the errors generated due to the MAPI/AD combination might resolve to provide a smoother experience .