Probad lo que dice Churly. Yo sí uso el KMail y la opción esa está en Preferencias -> Configurar KMail.
En el apartado de "Red", le dáis a la pestaña de "Enviando", marcáis la cuenta que uséis y "Modificar". Dentro está la opción de Autentifiación, que debéis pasarle el usuario y contraseña.
Churly: el Evolution no es un poco pesado, o eso ha cambiado? Cuando lo probé hace tiempo me lo pareció, aunque yo tb. andaba justo de equipo. El KMail me pareció más liviano.
Saludos.