The default Vim provided by Ubuntu 16.04 even did not have Python support. That's insane. 

I say, what if I wanted to use Vim as a Python IDE in Linux as before? Ubuntu, you can't be so careless.

My previous Vim Python IDE settings on Github: https://github.com/xros/dotfiles

Using this command to check whether it has

vim --version

I have compiled one deb package for Ubuntu 16.04

Remove old ones and install this one

sudo apt-get remove vim-tiny vim-common vim-gui-common

Go install dependencies 

mkdir /usr/share/vim/vim74/ -p

Go get it

https://drive.google.com/open?id=0BzL1CwVspEkiS2lwUURsQUMtYUU

dpkg -i vim_7.4.1952-1_amd64.deb

Check it out

vim --version

To make it the default editor

sudo update-alternatives --install /usr/bin/editor editor /usr/bin/vim 1
sudo update-alternatives --set editor /usr/bin/vim
sudo update-alternatives --install /usr/bin/vi vi /usr/bin/vim 1
sudo update-alternatives --set vi /usr/bin/vim

More info here:

https://github.com/Valloric/YouCompleteMe/wiki/Building-Vim-from-source

Have fun!