Tenía un par de días que me estaba sucediendo este error con CheckGmail la aplicación de la que les hablé en este post.
Estuve buscando un poco y parece ser que hace un año aproximadamente sucedió lo mismo debido a que google modifica la forma en que se autentifican en las cuentas. En esa ocasión se al igual que para este caso se resuelve todo descargando la versión svn (en desarrollo). Los pasos se explica en las siguientes instrucciones:

1. Instala el paquete subversion ejecutando en una terminal (Aplicaciones/Accesorios/Terminal):
   sudo apt-get install subversion
   Nota: Este paso es diferente para cada distribución.
2. Descarga el último paquete de Checkgmail con el comando:
   svn co https://checkgmail.svn.sourceforge.net/svnroot/checkgmail checkgmail
3. Cambia la dirección a la carpeta que se ha descargado con:
   cd checkgmail
4. Copia el binario a la carpeta /usr/bin, esto reemplazará el binario actual con el svn.
   sudo mv checkgmail /usr/bin/checkgmail
5. Da permisos de ejecución al nuevo binario con:
   sudo chmod +x /usr/bin/checkgmail

Lanza checkgmail de nuevo y prueba a conectarlo, edita las preferencias si es necesario. Ya puedes borrar la carpeta checkgmail que se ha generado en el paso 2. Gracias zeehio.
Saludos.

|Vía: Mundogeek.
|Relacionado:

• CheckGmail – Notificador de Gmail.
• Activar contraseña encriptada en Checkgmail.