O pacote vlc está localizado no repositório universe , que pode estar desativado em seu sistema.
Para ativá-lo, execute o comando abaixo:
sudo add-apt-repository universe
Em seguida, atualize suas listas de pacotes:
sudo apt-get update
Agora você deve conseguir instalar o vlc :
sudo apt-get install vlc