Vaya dios a saber que paso, pero el mantenedor se olvido de omitir config.inc.php al actualizar el paquete.
Este es el error:

“#1045 – Access denied for user ‘root’@'localhost’ (using password: NO)”

Para solucionarlo, pasarse por:

/etc/phpmyadmin/config/config.inc.php

Y corregir la linea que dice:

$cfg['Servers'][$i]['auth_type'] = ‘config’;

Cambiarla por http o cookie, dependiendo de lo que prefieran:

$cfg['Servers'][$i]['auth_type'] = ‘http’;

Si tienen caracteres raros en la linea de host, entonces es probable que alguien haya explotado una vulnerabilidad en su servidor.

Actualización: Al final parece que no es un problema del desarrollador que mantiene el paquete de phpmyadmin, sino que es una vulnerabilidad de Debian en dicho paquete. Tengo que revisar un poco más, pero si es el caso, hay que tener especial cuidado!