O Vim deve ser instalado por padrão em todas as máquinas. Além disso, esse comando deve funcionar bem. Você pode querer tentar estes:
sudo apt-get install vim-tiny
para o modo de linha de comando ou:
sudo apt-get install vim-gnome
para a edição completa da GUI.