Não me sinto bem com o upgrade do apt-get que a maioria das respostas sugere.
Isso ocorre principalmente por dois motivos.
Quando não é necessário atualizar todos os pacotes, por que você faria isso?
Nem todos os pacotes atualizados funcionam de maneira tão eficiente quanto o já instalado.
Eu sugiro usar o terminal e usar:
sudo apt-get install vlc
Agora digamos que você tenha dependências não atendidas para vlc-nox como
The following packages have unmet dependencies:
vlc : Depends: vlc-nox (= 2.1.6-0ubuntu14.04.2) but it is not going to be installed
Depends: libvlccore7 (>= 2.1.0) but it is not going to be installed
Recommends: vlc-plugin-notify (= 2.1.6-0ubuntu14.04.2) but it is not going to be installed
Recommends: vlc-plugin-pulse (= 2.1.6-0ubuntu14.04.2) but it is not going to be installed
E: Unable to correct problems, you have held broken packages.
Agora apenas adicione o nome das dependências ao comando.
sudo apt-get install vlc vlc-nox
Continue adicionando dependências até obter um início de instalação claro.
Uma coisa a notar: enfrentei problema de versão com uma das dependências.
Dependências foi instalado, mas da versão mais antiga.
The following packages have unmet dependencies:
libvlccore7 : Depends: vlc-data (= 2.1.6-0ubuntu14.04.2) but 3.0.0~~git20150319+r59816+33~ubuntu14.04.1 is to be installed
Use a limpeza para resolver esse tipo de problema.
apt-get purge vlc-data
e, em seguida, execute o comando de instalação. No meu caso acabou sendo.
sudo apt-get install vlc vlc-data vlc-nox libvlccore7 vlc-plugin-notify vlc-plugin-pulse
e Voila! Espero que ajude.