Ok, descobri sozinho. Mas eu acho que o problema pode ser que eu não expliquei bem as coisas na pergunta
Instalei o hamachi Linux beta usando dpkg -i package.deb
. Por alguma razão, o dpkg não instalou dependências, o que fez o apt pânico. A instalação manual não funcionou.
No entanto, é exibido que você precisa executar apt-get -f dist-upgrade
para que as depedências funcionem. Então combinou tudo e hamachi trabalhou
Espero que isso ajude alguém