Tente editar o apache2.conf ou o httpd.conf
sudo nano /etc/apache2/apache2.conf
Certifique-se de ter lá
include /etc/phpmyadmin/apache.conf
alias /phpmyadmin /usr/share/phpmyadmin
E que eles não são comentados. Não tenho certeza sobre os caminhos. O primeiro incluirá o arquivo de configuração do phpmyadmin. O 2º disponibilizará o phpmyadmin no 127.0.0.1/phpmyadmin. Eu teria que ver esses arquivos de configuração. Tente coisas diferentes reiniciando o apache em cada alteração:
sudo service apache2 restart