Instale o VIM atual do ppa no raring do Ubuntu 13.04

sudo apt-add-repository ppa:nmi/vim-snapshots
sudo apt-get update
sudo apt-get install vim-gnome

Isso irá instalar um VIM mais atual no ubuntu sem ter que compilar a partir do código-fonte. Depois, https://github.com/Valloric/YouCompleteMedeve funcionar.