Utilizo uma abordagem indireta. Não sincronizo diretamente com o ubuntu, mas sim com os contatos do gmail. No evolution posso ver, e editar os contatos do gmail então o resultado final é a mesma coisa para mim.

Sincronizo os contatos do celular usando a própria ferramenta nativa de sincronização do meu E51 pelo wifi.

Existem ferramentas mais completas como o goosync e o scheduleworld que sincronizam também a agenda e a lista de tarefas. Eu usava o scheduleworld e funcionava bem (usava o syncevolution para sincronizar o scheduleworld com o evolution), mas passou a ser pago.

Não lembro agora onde achei como configurar mas se você não achar eu te passo as configurações que estão no meu celular.

Na verdade, esse tópico é muitooo antigo e é bem provável que o autor dele nem precise mais disso.

Maaas caso esteja disposto a fazer o tutorial, até pode ser uma boa para enriquecer o fórum.
O que acha? 

Hoje em dia o pessoal usa bastante o Ubuntu One Mobile que, na minha opinião, é uma ótima alternativa!
Ele tem suporte a Android, iPhone, BlackBerry, Nokia e vários outros dispositivos.
Em breve rodará no desktop Windows também.

Uma outra opção, talvez não tão interessante assim, seria o Memotoo.
Ele é um serviço pago que sincroniza tudo o que der para imaginar!
Tem a versão gratúita também, mas com limites de uso.



Exemplos de sincronização: celulares, Thunderbird (inclusive com iCalendar), Kontact, Android, Gmail, Facebook, iPhone, Evolution, Google Calendar, Nokia, LG, Sony Erickson, HTC, SyncML Server, BlackyBerry, Yahoo!, Skype, Windows Mobile, Twitter, Samsung, Maemo, Xing, AOL, Viadeo, Firefox, LinkedIn, iPod, iPad, Windows Live, Mac OS X, Outlook, Linux, Task Coach, Windows, Sunbird (iCalendar), Outlook Express e muito mais!

Nesse canal do Youtube tem alguns vídeos deles: http://www.youtube.com/user/MEMOTOO1#p/u

Pessoalmente, não pagaria por um serviço assim.
Mas como ele tem muitas opções e se eu fosse usá-las realmente, acho que pode ser uma boa.

Eu já prefiro o Google.
Sincroniza automaticamente em qualquer lugar e não fica dependendo de sentar o bundão na cadeira pra ficar "emparelhando" as coisas.  
Fez alteração, sincronizou na hora!

http://ubuntuforum-br.org/index.php?topic=71278.0

Quanto a pagar pela internet, R$ 0,50 da TIM por dia quebra um galhão.
Se bem que não sei quanto tempo dura isso!

E sem falar dos vários pontos de acesso sem fio que tem por ai!
Na minha faculdade (que é bem lesada em suporte ao aluno) a gente usa numa boa.

Não que sincronizar por bluetooth ou internet seja melhor ou pior.
Depende do uso da pessoa!