Se eu entendi corretamente, vlc está no repositório universe . Se não estiver disponível, você deve ativar esse repositório. Você pode fazer isso com os seguintes comandos (ou com alguma ferramenta GUI, por exemplo synaptic ).
sudo add-apt-repository universe
sudo apt-get update
então deve funcionar para instalar o vlc com
sudo apt-get install vlc