Isso parece o caso em que você está tentando executar um binário ELF de 32 bits, em uma instalação de 64 bits, sem ter as bibliotecas de 32 bits instaladas. Se for esse o caso, instalar o pacote chamado ia32-libs deve permitir que você execute este binário adb.