Verifique sua lista de fontes /etc/apt/sources.list
é como deveria ser. Executar
sudo apt-get update
para baixar o banco de dados de pacotes. Então tente novamente.
Se tudo mais falhar, talvez você possa encontrar mais conselhos e novas versões para compilar a partir da fonte em www.vim.org .