Ubuntu 16.04 by default install Vim compiled against Python 3.5 interpreter, which is not immediate obvious but becomes a pain in the ass after you discover that even after installing Jedi and python-jedi, you're still getting the error message:
When opening a file with Python code.
To get things working for your Python 2.7 code, you might need to uninstall your current Vim related packages and install the following:
$ dpkg-query -l 'vim*'
- vim-addon-manager
- vim-common
- vim-gnome-py2
- vim-gtk3-py2
- vim-gui-common
- vim-nox-py2
- vim-python-jedi
- vim-runtime
$ dpkg-query -l 'vim*'