Você precisa forçar o apt-get a reinstalar os arquivos do pacote, já que um comando regular 'install' pegará atalhos. Você também pode precisar reinstalar alguns dos outros pacotes relacionados ao vim. Tente isto:
sudo apt-get install --reinstall vim vim-common