Tente dar uma olhada no arquivo deb convertido usando seu Gerenciador de arquivos preferido. Ele contém os arquivos que você deseja? (Dê uma olhada no data.tar.gz dentro do arquivo deb)
Se isso acontecer, eles devem estar no seu disco, onde eles estão localizados no arquivo. Verifique estes locais no seu disco. Se os arquivos estão lá, qual é o seu problema?
Se você está faltando apenas o arquivo de inicialização (aquele listado no Dash / Application Menu), crie um você mesmo.
EDIT: Você tentou instalar as fontes. Isso não vai funcionar, é claro. O repositório minetest contém pacotes pré-compilados, por que você não os usa. Ou apenas obtê-lo via APT, como indicado em Downloads / Debian.