Solucionado
apt-get remove --purge mysql-server mysql-client mysql-common
apt-get install mysql-server mysql-client mysql-common
Pero con una diferencia
Cuando me fallaba, estaba en una cuenta de usuario, sin privilegios de administrador. Habría una consola, hacia "su root", y desde aquí, realizaba la reinstalación, dando los fallos anteriormente comentado.
La solución la encontré logendo como root, y realizando los comandos anteriores.
Saludos.