Tente reconfigurar o phpmyadmin fazendo o seguinte
sudo dpkg-reconfigure phpmyadmin
Se isso não resolver o problema, limpe o phpmyadmin e reinstale o phpmyadmin.
sudo apt-get --purge remove phpmyadmin
Se ainda tiver problemas. Eu recomendo remover a pilha LAMP e instalar usando o seguinte comando.
sudo apt-get install lamp-server^