Did you notice that vi is pretty much feature-free on newer Debian systems? it doesn't even have syntax coloring.

The default vi package installed on Debian Lenny, and Ubuntu is vim-tiny, which is really restricted and very appropriate for really, really small environments.

To update, install vim-nox for the real thing.

If you want the GUI version, install vim-full, which basically installes vim-gnome.

vim-gnome will give you several more packages, listed below. The list of dependencies is not important on a desktop or laptop, but matters on a small VM because of the space required. All specific version dependencies here are for Ubuntu 8.04 LTS.

Depends: libart-2.0-2 (>= 2.3.18), libatk1.0-0 (>= 1.20.0), libbonobo2-0 (>= 2.15.0), 
libbonoboui2-0 (>= 2.15.1), libc6 (>= 2.7-1), libcairo2 (>= 1.5.0), libgconf2-4 (>= 2.13.5), 
libglib2.0-0 (>= 2.15.4), libgnome2-0 (>= 2.17.3), libgnomecanvas2-0 (>= 2.11.1), 
libgnomeui-0 (>= 2.17.1), libgnomevfs2-0 (>= 1:2.17.90), libgpmg1 (>= 1.19.6-1), 
libgtk2.0-0 (>= 2.12.0), libice6 (>= 1:1.0.0), libncurses5 (>= 5.6+20071006-3), 
liborbit2 (>= 1:2.14.10), libpango1.0-0 (>= 1.19.3), libperl5.8 (>= 5.8.8), 
libpopt0 (>= 1.10), libruby1.8 (>= 1.8.6.111), libsm6, libx11-6, libxt6, 
python2.5 (>= 2.5), vim-common (= 1:7.1-138+1ubuntu3), vim-gui-common (= 1:7.1-138+1ubuntu3), 
vim-runtime (= 1:7.1-138+1ubuntu3)

vim-nox has a smaller list of dependencies, some of which you may want anyway:

Depends: libc6 (>= 2.7-1), libgpmg1 (>= 1.19.6-1), libncurses5 (>= 5.6+20071006-3), 
libperl5.8 (>= 5.8.8), libruby1.8 (>= 1.8.6.111), python2.5 (>= 2.5), 
vim-common (= 1:7.1-138+1ubuntu3), vim-runtime (= 1:7.1-138+1ubuntu3)