Como você tem uma nova instalação, existem repositórios que precisam ser atualizados. Execute estes comandos:
$ sudo apt update
$ sudo apt upgrade
$ sudo apt dist-upgrade
$ sudo apt install vlc
Quando tento instalar algo do Ubuntu Software Center, não encontro nada.
Por exemplo, o VLC. Eu tentei baixá-lo do site oficial, e isso me leva de volta ao software do Ubuntu. Eu tentei no terminal e não consigo encontrar o repositório. Isso acontece com qualquer programa, exceto os programas que eu já tenho, como o Firefox.
Estou usando o Ubuntu 16.04.1 em um i5 2410m e 8GB de RAM.
Como você tem uma nova instalação, existem repositórios que precisam ser atualizados. Execute estes comandos:
$ sudo apt update
$ sudo apt upgrade
$ sudo apt dist-upgrade
$ sudo apt install vlc