Experimente o Gerenciador de Pacotes Synaptic
Você já tentou instalar o VLC usando o Gerenciador de Pacotes Synaptic? Faça o download do Synaptic a partir do Centro de Software ou de aqui e procure por VLC. Se você o instalou em seu sistema, ele mostrará qual versão você instalou. Marque o VLC (se estiver instalado) para remoção completa (somente VLC) e clique em aplicar. Depois de ter sido removido, procure novamente por VLC e, desta vez, marque-o para instalação. Ele marcará automaticamente as dependências não atendidas. Clique em aplicar para instalá-lo novamente.
Para os vídeos
Para os vídeos, vá até o centro de software e procure por vídeos e clique em mais informações. Verifique a instalação do codec do GStreamer nos complementos opcionais e clique em aplicar alteração.
Espero que isso seja útil.