Por fin he conseguido configurar Android en mi Ubuntu 6.06. Despues de dar una y mil vueltas, probando mil y una combinaciones distintas puedo juguetear con el nuevo "invento" de Google.

Por si alguien en mi misma situación tiene problemas para hacer funcionar Android pongo a continuación los pasos que he seguido:

1. Instalar Automatix a través del Gestor de Paquetes Synaptic (Buscar automatix).
2. Mediante Automatix, instalar el Sun Java 1.6 JDK (Está en la sección Programming Tools).
3. Descargar Eclipse.
4. Descomprimir el fichero descargado anteriormente (En la carpeta /opt mismo).
5. Ejecutar Eclipse e instalar el plugin de Android (ADT) tal y como se indica en la página de Google Android.
6. A jugar.

En principio siguiendo estos pasos todo debería funcionar correctamente. Para cualquier problema, los comentarios :)