Você pode usar um repositório externo
sudo add-apt-repository ppa:videolan/stable-daily
sudo apt-get update
sudo apt-get install vlc
Isso instalará a versão mais recente
UPDATE
primeiro habilite o Universo
sudo add-apt-repository "deb http://archive.ubuntu.com/ubuntu $(lsb_release -sc) universe"
tente isso
sudo ppa-purge ppa:videolan/stable-daily
sudo apt-get update
sudo apt-get install vlc
Se o ppa-purge não estiver instalado, você pode instalar usando
sudo apt-get install ppa-purge
Ou use o comando add-apt-repository -r