Acontece que o problema foi que havia um script não relacionado em /etc/init.d
que estava quebrando o dpkg. A correção foi remover o script incorreto. O caso geral seria verificar todos os seus scripts init.d e verificar se eles realmente rodam antes de tentar executar o apt.