I finally found this on the Evolution bugzilla: http://bugzilla.gnome.org/show_bug.cgi?id=323619 It's a lack of support for NTLMv2 and it's been a known problem since December 2005. The bug is still not triaged so I am going to try and triage it myself. CC