A coexistência de interfaces gráficas diversas num mesmo sistema sempre é algo complexo.
É uma instalação complexa, na verdade todo um novo ambiente gráfico colocado juntamente com a interface gráfica do Ubuntu padrão (=Unity), com escolha no logon, o que torna a remoção igualmente uma tarefa complexa.
Observe o log da instalação, no caso feita sobre uma instalação experimental live-iso do Ubuntu 16.04.2 padrão (=Unity):
http://paste.ubuntu.com/24190232/É difícil fazer uma remoção completa sem ser de uma forma manual bastante trabalhosa e demorada, pois demandaria ir analisando passo a passo tudo o que foi feito quando da instalação para poder reverter e mesmo assim ainda restaria identificar o que possa ter sido alterado a partir daquele próprio ambiente instalado, isto é, a partir dele próprio, com ele já instalado, que em tese poderia ter armazenado ou alterado arquivos que não constem no log inicial da instalação.
De toda forma, a remoção deve em princípio obedecer à ordem inversa daquela que foi instalada e ainda é melhor usar o ppa-purge para auxiliar na remoção e evidentemente é melhor que seja feita a partir da interface gráfica do Unity e não dela própria.
Como disse, numa instalação experimental a partir de um live-iso foi possível remover, mas não posso garantir aí no seu sistema, que é uma instalação real, vá igualmente funcionar ou não deixar outras sequelas, só mesmo experimentado para descobrir.
Instale o ppa-purge como ferramenta auxiliar:
sudo apt install ppa-purge
Agora iniciando a remoção pela ordem inversa da instalação:
sudo apt-get remove --purge -y mate-menu mate-dock-applet
sudo apt-get remove --purge -y mate-desktop-environment-extras
sudo apt-get remove --purge -y mate-desktop-environment
sudo apt-get remove --purge -y mate-desktop-environment-core
removendo a ppa com ppa-purge:
sudo ppa-purge -y ppa:ubuntu-mate-dev/xenial-mate
fazendo remoção do menu:
sudo apt-get remove --purge -y mate-menu*
fazendo autoremove dos pacotes:
sudo apt-get -y autoremove
Reinicie a sessão