No Ubuntu 17.10 , a compilação é a solução que funcionou para mim:
Inspirado diretamente na essa essência , fiz o seguinte:
sudo apt-get remove --purge vim vim-runtime vim-gnome vim-tiny vim-gui-common
sudo apt-get install checkinstall
sudo rm -rf /usr/local/share/vim /usr/bin/vim
cd /tmp && git clone https://github.com/vim/vim
cd vim/src
make distclean
cd ..
./configure --enable-multibyte --enable-perlinterp=dynamic --enable-pythoninterp=dynamic --with-python-config-dir=/usr/lib/python2.7/config-x86_64-linux-gnu --enable-cscope --enable-gui=auto --with-features=huge --with-x --enable-fontset --enable-largefile --disable-netbeans --with-compiledby="put your name here" --enable-fail-if-missing
make
sudo make install
sudo ln -s /usr/local/bin/vim /usr/bin/vim
Não se esqueça de adaptar os parâmetros ./configure
para ter todos os outros recursos de que você precisa.
Agora você pode abrir o vim e executar o comando :echo has('python')
para confirmar que você tem o python 2 ativado.