Eu peguei a opção nuclear e executei este script
#!/bin/bash
for pkg in 'dpkg --get-selections | awk '{print $1}' | egrep -v '(dpkg|apt|mysql|mythtv)'' ; do apt-get -y --force-yes install --reinstall $pkg ; done
Ele passa por tudo instalado e o reinstala. O rato funciona agora.