Eu tive o mesmo problema, removi-o removendo vim-gnome e instalando vim-gtk :
sudo apt-get remove vim-gnome
sudo apt-get install vim-gtk
Eu configurei meu computador para o novo Ubuntu 16.04 hoje. Eu já instalei o vim-gnome. Ao trabalhar com isso, está tudo bem. Mas quando eu fecho o gvim eu recebo essa mensagem no terminal:
(gvim:5834): GLib-GObject-WARNING **: cannot retrieve class for invalid (unclassed) type '<invalid>'
Não está causando nenhum problema, ainda quero resolver esse problema antes que ele possa afetar algo.
Eu tive o mesmo problema, removi-o removendo vim-gnome e instalando vim-gtk :
sudo apt-get remove vim-gnome
sudo apt-get install vim-gtk