Au préalable il faudrait s'assurer que niveau réseau, tout est ok. Si firefox marche c'est effectivement un problème lié à évolution. Vérifie que tu as correctement configuré :
- le port du serveur smtp (en général 25),
- le nom du serveur smtp (a priori aliceadsl.smtp.fr),
- la méthode d'authentification (a priori aucune).

Si tu ne t'en sors pas avec evolution tu peux installer thunderbird. Pour cela tu peux passer par synaptic ou directement utiliser la console :
http://doc.ubuntu-fr.org/terminal
http://doc.ubuntu-fr.org/synaptic

Dans une console :

sudo aptitude update
sudo aptitude safe-upgrade
sudo aptitude install thunderbird thunderbird-locale-fr