Ao instalar a partir de um arquivo .deb, as dependências também não são instaladas automaticamente, como seria o caso se o Hamachi fosse um pacote completo.
No entanto, é fácil instalar a dependência por conta própria neste caso. Abra um terminal e faça
sudo apt-get install lsb-core
Em seguida, tente instalar novamente a partir do arquivo .deb.