O mesmo problema ocorreu comigo quando eu estava tentando instalar o vim no meu Ubuntu 12.04.
Eu tentei o seguinte e funcionou para mim: -
sudo apt-get update
e depois disso, sudo apt-get install vim
Depois de executar esses comandos, ele começou a funcionar corretamente.