Depois de jogar com ele, vejo o que está acontecendo agora. Você dpkg -i whatever.deb e irá carregá-lo na máquina com alguma capacidade quebrada, mas não o instalará completamente, então você executa o apt-get -f install e ele irá baixar e corrigir as dependências para você e então ele irá completar o processo de instalação do pacote deb. Não é bonito, mas funciona e eu estou feliz.