(Eu queria apenas adicionar um comentário à resposta de Rho, mas eu sou novo aqui, então) Eu acredito que a purga fará o trabalho. Se você:
sudo apt-get remove --purge w3c-markup-validator
Ou, caso isso não funcione:
sudo dpkg --purge w3c-markup-validator
Depois siga a sequência de Rho, ela será corrigida.
sudo dpkg --configure -a
sudo apt-get install -f
sudo apt-get update
sudo apt-get install -f
Atenciosamente.