Ya lo he solucionado, al final era muy simple, os pongo aqui los pasos por si a alguien le pasa:
1 - Instalar Apache, Mysql y Php5 (sudo apt-get install apache2 mysql-server php5)
2 - Instalar phpMyAdmin (sudo apt-get install phpmyadmin)
3 - Mover la carpeta a www, darle permisos y reiniciar apache
mv /usr/share/phpmyadmin /var/www
chown -R (nombre de usuario sin parentesis) /var/www/phpmyadmin
4 - Reiniciar apache (/etc/init.d/apache2 restart)
5 - Iniciar phpMyAdmin (En el navegador: localhost/phpmyadmin)
Y con eso ya deberia funcionar
Gracias por vuestras respuestas