Hoy he podido por fin configurar mi cuenta de Gmail en Evolution.
La configuración que utilice es la que indica Google:

• Servidor Entrante (IMAP) con SSL:imap.gmail.com
  Usar SSL: Sí
  Puerto: 993
• Servidor de Correo Saliente:
  smtp.gmail.com(usar autenticación)
  Usar autenticación: Sí
  Usar STARTTLS: Sí (en algunos clientes se denomina SSL)
  Puerto: 465 ó 587
• Nombre de Cuenta:
  tu nombre de usuario de Gmail (incluido @gmail.com)
• Dirección de correo electrónico:tu dirección de correo electrónico completa de Gmail (nombredeusuario@gmail.com)
• Contraseña:tu contraseña de Gmail

Para hacer que funcione el envio de correos utilice el puerto 587