NOTA: A partir del 1 de junio de 2011 la actual sincronización de contactos de Ubuntu One para móviles dejará de estar activa. Estamos dejando de dar soporte a nuestro servicio actual para poder centrar nuestra energía en el lanzamiento de un servicio mucho mejor antes de lo que podríamos hacer de otra manera.
https://wiki.ubuntu.com/UbuntuOne/PhoneSync/
Probablemente no sea la respuesta que buscabas. Yo mismo soy usuario de Ubuntu (3 PC, sólo uno de arranque dual) y Android (2 teléfonos Android). Voy a recomendar la migración a los contactos de Google. Supongo que todos tus contactos están almacenados en "Teléfono" (si no los estás sincronizando) La mayoría de los teléfonos pueden exportar fácilmente tus contactos a una tarjeta SD y luego reimportarlos. Cuando se te pregunte, selecciona tu cuenta de google, no "Teléfono". Debes seleccionar sólo los contactos de Google para que sean visibles, para evitar duplicados.
Si quieres sincronizar tu aplicación de correo de escritorio con el servicio online, y usas Thunderbird (o te parece bien), instalando zindus podrás sincronizar los contactos de thunderbird y gmail. De todos modos, los contactos de G y los de Android se sincronizan automáticamente con las opciones correctas. En resumen: Si quieres una solución simple en línea, selecciona los contactos de google (gmail) Si quieres un cliente de correo de aplicación de escritorio sin conexión, añade Thunderbird +zindus a la ecuación