Se alguém acabar aqui procurando uma solução, o problema é provavelmente um bug que surgiu no Evolution 3.5 quando o processamento de TNEF passou de um plugin para um módulo.
Foi corrigido no Evolution 3.12.9+ e no 3.13.8+, portanto, você precisará usar uma distribuição que ofereça um deles ou superior, que é o caso de Ubuntu GNOME 15.04 e acima (mas 16.04 é recomendado, como 15.04 não é mais suportado, e 15.10 só tem mais 2 meses de suporte em o tempo da escrita).