Você pode tentar atualizar todos os seus pacotes antes de tudo (isso incluirá o centro de software):
sudo apt-get update && sudo apt-get upgrade -y
Quando você atualizou todos os pacotes do seu sistema, você pode tentar instalá-lo novamente a partir do centro de software, ou você pode instalar o VLC diretamente do terminal (aw yeah) digitando isto:
sudo apt-get install vlc