Here's what I do to get python support in vim
apt-get install -y python-software-properties software-properties-common
# add this repo so that vim has python 4? compiled in to support plugins like gundo
add-apt-repository -y ppa:pi-rho/dev
this install a massive vim build that will give you everything
apt-get install -y vim-gtk
Running these commands on Ubuntu 16.04 worked for me about 2 weeks ago.
problems with versions
The way this can cause problems is that by default,
apt-get will install the newest version of the package, usually the pi-rho repo version is far newer than say 14.04's vim-gtk package and apt will install the pi-rho version. However on 16.04 the ubuntu universe? repo for vim-gtk has been neck and neck for versions with pi-rho - but the ubuntu package doesn't seem to have python support. ( I may be wrong on this though ).
so ideally you would run
apt-cache policy vim-gtk
prior to install to check that apt will install pi-rho, if not you will have to run something like
sudo apt-get install vim-gtk=<version>