Eu instalei o ubuntu-desktop, isso parece ter resolvido o problema.
Editar: Para instalar o ubuntu-desktop, abra o terminal e digite
sudo apt-get install ubuntu-desktop
Como mencionado na pergunta, eu estava rodando o MATE (variante do gnome2 até onde eu posso dizer), não o Unity que vem no pacote ubuntu-desktop.