Для моего случая я сначала удалил установленный gvim с помощью:
sudo apt-get remove --auto-remove vim-gtk3
Затем я установил gvim с помощью:
sudo apt install vim-gtk3-py2
Кстати, я использую Vim8 из:
sudo add-apt-repository ppa:jonathonf/vim