Eu realmente já tentei várias das soluções postadas em questões semelhantes, não importa qual abordagem eu tente, só posso instalar os seguintes pacotes:
ii libvlc5 2.0.3+git20121229+r489-0~r41~precise1 multimedia player and streamer library
ii libvlccore5 2.0.3+git20121229+r489-0~r41~precise1 base library for VLC and its modules
ii vlc-data 2.0.3+git20121229+r489-0~r41~precise1 Common data for VLC
ii vlc-nox 2.0.3+git20121229+r489-0~r41~precise1 multimedia player and streamer (without X support)
Eu até ontem tive o vlc player instalado, mas uma tentativa fracassada de instalar o skype removeu uma tonelada de pacotes do meu sistema, sendo vlc um deles.
Aqui está um link para a saída capturada sempre que eu executo o sudo apt-get install vlc:
link
O problema era que o libqtcore4 tinha sido atualizado, enquanto um grande número de pacotes libqt ainda dependia da versão anterior. A solução foi fazer o downgrade da libqtcore4 e eu consegui instalar o VLC com sucesso depois de fazer isso. Aqui está um ótimo post sobre pacotes de downgrade no Ubuntu se você estiver enfrentando um problema similar:
O VLC está no próprio Ubuntu Software Center. Abra o seu Centro de Software e digite VLC no campo de pesquisa. você vai encontrá-lo para instalar.