OK, tem sido um monte de pesquisa, mas parece que o problema é que o adb e algumas outras ferramentas SDK ainda usam algumas bibliotecas de 32 bits que foram preteridas e não são mais fornecidas com a versão mais recente do Ubuntu 64 ....
Espero que este problema seja resolvido em breve. Enquanto isso, trabalhei com:
sudo apt-get install lib32z1 lib32ncurses5 lib32bz2-1.0
sudo apt-get install lib32stdc++6
E até agora está funcionando como esperado.
Espero que esta resposta evite que outras pessoas passem um dia inteiro procurando o problema:)