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