I think your problem is that you're running 64bit Debian but forgot to install ia32-libs.
Because the phones aren't 64bit, so there is no 64bit version of adb. You need the ia32-libs.
After install the ia32-libs, open Android SDK Manager, then uninstall all the tools and reinstall them.
You should no longer get the adb error.