Eu tive um problema semelhante. Não sei por que, mas usar o vlc-wrapper
em vez de cvlc
ou vlc
executando o programa como raiz através de gksudo
ajudou. Assim:
gksudo vlc-wrapper
verifique também se ffmpeg
e outros pacotes relacionados estão instalados:
sudo apt-get install ffmpeg*