mate-terminalиспользует VTEвиджет эмуляции терминала, который поддерживает расширенную 256-цветовую палитру (как почти каждый графический эмулятор терминала делает сегодня; и, кстати, VTEдаже поддерживает прямые истинные цвета). Первые 16 записей этой палитры (унаследованные) можно настроить в диалоговом окне «Настройки», остальные - нет.
mate-terminalтакже экспортирует TERM=xterm-256colorпо умолчанию, поэтому vimзнает, что он поддерживает 256 цветов и выбирает цветовую схему соответственно.
Возможный обходной путь - вернуть только 16 цветов, не сообщая vim, что эмулятор терминала поддерживает больше, вы можете сделать это с помощью export TERM=xterm. Я бы предпочел, однако, посмотреть в настройках vim и настроить его на использование желаемых цветов, даже если он знает, что доступно 256 цветов.