Isso significa que você não atualizou muitos pacotes do sistema em muito tempo, ou você não está instalando o pacote vlc a partir do repositório.
Executar
sudo apt-get update
e, em seguida, execute
sudo apt-get upgrade
e, em seguida, execute
sudo apt-get install vlc
Se você ainda enfrentar problemas, execute
sudo apt-get -f install