O VLC não usa o gstreamer, ele usa seu próprio sistema. Ir para software & amp; atualizações e certifique-se de que universe / multi está selecionado e, em seguida, escolha vlc no Software Center. Um de seus servidores pode estar inativo, portanto, talvez seja necessário atualizar ou alterar o campo "download from:" para algo como o Servidor Principal.
Além disso, qual é o resultado de cat /etc/apt/sources.list