Eu recebi o mesmo erro ao tentar executar a instalação beta do Android-studio. Eu tentei várias opções, mas a que funcionou para mim foi:
sudo apt-get install openjdk-7-jdk
Não precisou fazer mais nada.
Mas, estou surpreso que
java -version
listou as mesmas 3 linhas antes e depois da instalação do jdk:
java version "1.7.0_55"
OpenJDK Runtime Environment (IcedTea 2.4.7) (7u55-2.4.7-1ubuntu1~0.13.10.1)
OpenJDK 64-Bit Server VM (build 24.51-b03, mixed mode)
e
echo $JAVA_HOME
gera espaços em branco, mas agora o android-studio está rodando.