А если сначала сделать
apt-get install mate-default
а потом
apt-get remove gnome3
Либо сначала снесли третьегном, а потом ставить мэйт, как думаете будут проблемы?
Можно в любом порядке, но я бы сначала mate поставил, а потом gnome3 удалял, так как общие пакеты в зависимостях наверняка найдется - придется заново устанавливать. Вы только учтите, что пакета gnome3 нету, есть gnome3-default. Кроме того, удаление метапакета не удалит все его зависимости. Нужно самому ручками в строке удаления каждый указывать. На вскидку из того, что точно можно удалять - mutter, gnome-shell, gnome-control-center, gnome-settings-daemon, gnome-session, gnome-tweak-tool, nautilus. evince, totem, rhythmbox, eog, gedit.