У меня была такая же проблема на моей новой 64-битной установке Ubuntu, и путь был задан правильно.
Таким образом, which adb
будет разрешен правильно, но попытка его запустить не удастся с adb: command not found
.
Очень полезные ребята из # android-dev подсказали мне решение, а именно то, что 32-битные библиотеки не были установлены. На моих предыдущих компьютерах это, вероятно, использовалось как зависимость для другого пакета.
В Ubuntu (возможно, также и в других Debian), работающей [sudo] apt-get install ia32-libs