The cause seems to be rather obvious: you use a version of Vim that's not built with python support.
The solution is also rather obvious: install a Vim built with python support.
If you use a graphical environment:
$ sudo apt-get install vim-gnome
If you don't:
$ sudo apt-get install vim-nox