[rammark]

Try installing vim-gtk instead of vim-gnome.

[marshray]

IIRC, it would have required me to add the 'universe' repository.