Existe uma longa postagem longa com uma 'correção feia' para este problema: eu não sei o que mais isso iria quebrar.
Em uma janela de terminal, edite /etc/init.d/udev
da seguinte forma:
sudo nano /etc/init.d/udev
Após o ### END INIT INFO, adicione:
sair 0
Salvar e sair.
sudo dpkg --configure -a
sudo apt-get upgrade