Por favor, atualize seus repositórios primeiro, seguindo o comando (verifique se você recebe algum erro durante a atualização):
sudo apt-get update
Em seguida, tente isto:
sudo apt-get -f install vlc
A opção -f tentará instalar o pacote com força.
Se nada funcionar, por favor tente remover as dependências ou limpar a vlc.