Sistema<Administración<Gestor de paquetes Sinaptic, en buscar: vlc, enter.
Por lo menos deberías tener en verde lo que se ve en la imágen.
Para instalar, desintalar, debes posicionarte en la casilla y darle clic con el derecho, donde te van a aparecer las opciones. Luego aplicar.
Probá desinstalar completamente y luego volver a instalar.
Antes de todo esto en una terminal update, upgrade.