Se você instalou o phpmyadmin com apt - reconfigure-o no terminal:
sudo dpkg-reconfigure o phpmyadmin
Veja mais no link
Se necessário - verifique a configuração existente em /etc/apache2/conf-enabled - deve haver o symlink phpmyadmin.conf.
ou
você pode instalá-lo manualmente - a partir do link - baixe e descompacte o diretório raiz da web. Se você já tentou instalar o phpmuadmin com o apt - evite usar o phpmyadmin como nome de diretório, use o padmin, por exemplo. Em seguida, aponte para yoursite.net/padmin.