Recomendamos que você use o Catálogo de Endereços do Evolution.
Adicione-o no Centro de Software ou no terminal - sudo apt-get install evolution
Ou use o Kontact da área de trabalho do KDE - pode ser instalado com sudo apt-get install kontact
.
O smartphone deve sincronizar com os serviços on-line, sem necessidade de sincronizar contatos com o computador!
Pessoalmente eu prefiro o Thunderbird.