Em um sistema de 64 bits, você precisa das bibliotecas de 32 bits para o Android SDK:
Para o Ubuntu 13.04 ou abaixo:
sudo apt-get install ia32-libs
Para o Ubuntu 13.10 ou superior:
sudo apt-get install libgl1-mesa-dev:i386
As ia32-libs são um pacote de compatibilidade de 32 bits para sistemas de 64 bits, portanto, apenas disponíveis em tais sistemas. Se você já tem uma instalação de 32 bits, você precisa instalar o libGL separadamente:
sudo apt-get install libgl1-mesa-dev