Ok, finalmente consertei meu problema. Parece que a Canonical não gosta de atualizar seus repositórios com muita frequência. Então, é assim que instalamos uma versão de trabalho do minetest:
- Desinstale o minetest e o minetest-server do Ubuntu Software Center. (vá para a guia Instalado, o minetest está em Jogos)
- Pressione ctrl-alt-T e digite no console "sudo add-apt-repositório ppa: minetestdevs / stable"
- Se você não pôde desinstalar o minetest-server do centro de software, digite "sudo apt-get remove o minetest-server" ou ele não permitirá a instalação do minetest. (claro que durante todo esse tempo você pode não ter instalado o minetest-server, e nesse caso não se preocupe com isso)
- Digite "sudo apt-get install minetestc55". Quando o console terminar de fazer seus negócios, pressione Super / Start, pesquise Minetest e arraste o ícone para o Launcher.
- Aprecie.