Você tentou reinstalá-lo?
verifique se você atualizou tudo com
sudo apt-get update e sudo apt-get upgrade
eu tenho um erro semelhante quando eu atualizei para o Ubuntu 15.04, mas depois que eu atualizei tudo e reiniciei o pc, vlc funcionou bem, espero que ajude você também