Eu tive isso acontecer comigo também. Você terá que abrir um terminal. A primeira coisa é verificar se há dependências quebradas:
sudo apt-get install -f
Se isso não funcionar, eu limparia a vlc e reinstalaria:
sudo apt-get purge vlc*
sudo aptitude purge $(dpkg -l|grep ^rc|awk '{ print $2 }')
sudo apt-get update
sudo apt-get autoremove
sudo apt-get install vlc
Não tenho certeza se isso funcionará, mas informe-nos e posso ajustar, dependendo de seus resultados.