Recientemente instalé Ubuntu 13.10 64bits y me encontré con que no podía ejecutar el emulador ni el adb del SDK de Android.
Habiendome fijado en haber instalado la versión correcta del SDK no entendía porqué no funcionaba y me daba el error mencionado ademas de "No existe el archivo o directorio", traté de ejecutarlo directamente desde la consola y me daba el mismo error.
Despues de haber investigado encontré que tenía que instalar el paquete "ia32-libs" para solucionar la ejecución de un binario de 32bits en un sistema de 64bits pero no me dejó porque en Ubuntu 13.10 no existe el paquete. Esto se debe a que desde Ubuntu 13.04 los las librerias 32bits de pueden instalar sin problemas solo especificado la arquitectura al hacer "apt-get install" (sudo apt-get install nombrepaquete:i386 por ejemplo).
Haciendola corta encontré que las librerías de x86 que necesitaba eran libc6, gcc y ncurses entonces instalé los paquetes y listo.
sudo apt-get install libc6-i386 lib32stdc++6 lib32gcc1 lib32ncurses5
Ahora funciona sin problemas.