Primeiramente, tente executar o Evolution a partir de um terminal - você pode ver o que ele registra no STDERR e no STDOUT em busca de pistas sobre o que pode estar errado.
Com isso fora do caminho: a integração com o Exchange sempre foi um dos meus erros sobre mudar para o Linux em tempo integral e permanece assim. Nenhuma das duas abordagens para a Evolução é satisfatória, na minha opinião - tanto a biblioteca libmapi quanto a ews possuem bugs e falhas que os tornam frustrantes de usar a longo prazo.
Supondo que seu departamento de TI não tenha POP3 ou IMAP habilitado no servidor, sua melhor aposta será tentar o Outlook Web Access - versões mais antigas eram calças em navegadores não-IE, mas versões mais recentes são surpreendentemente robustas.
Provavelmente não é a resposta que você está procurando :-D