Cada vez que instalo phpMyAdmin en mi Elementary OS (o en Ubuntu) tengo el mismo problema. Intento acceder a localhsot/phpmyadmin y no se encuentra (Error Not Found). Para solucionarlo, debemos hacer lo siguiente:
Editamos /etc/apache2/apache2.conf
sudo vim /etc/apache2/apache2.confAñadimos la siguiente linea al final del archivo
Include /etc/phpmyadmin/apache.confReiniciamos Apache
sudo service apache2 restart