Bem, eu recomendo que você tente instalar as dependências digitando o cmd,
sudo apt-get -f install
Se isso não funcionar, tente instalar o navegador chromium, que instalará melhor libc dep que será menos agitado se você não estiver familiarizado com o tratamento de dependências.
sudo apt-get install chromium-browser
Agora instale o VLC, agora seu problema pode estar resolvido agora.
sudo apt-get install vlc
É isso.