Resolvi o problema. Removi o diretório "~/.evolution", fui ao gmail, movi todos e-mails para a Caixa de Entrada novamente e mandei o Evolution começar a baixar.
Ele baixou em 4 partes, acho que eram muitos emails. Então ele fez o downloads de uma parte dos emails e parou. Cliquei en Enviar e Receber novamente ele continuou e assim foi até o final.
[]s