Takže problém zřejmě není v Evolution, ale v tom, že máš blokovaný port 25, který je výchozí pro smtp přenos. Zkus ještě co Ti vypíše sudo iptables -L
(firewall), pokud jen něco takového Chain INPUT (policy ACCEPT)
target prot opt source destination
Chain FORWARD (policy ACCEPT)
target prot opt source destination
Chain OUTPUT (policy ACCEPT)
target prot opt source destination
pak máš firewall vypnutý a je potřeba hledat problém mimo Tvůj počítač.