¿Qué mensaje _exacto_ te enviaba al intentar instalar vlc? ¿Por qué no usas urpmi para instalar programas? urmpi te instala un programa y todas sus dependencias automágicamente
En mi opinión, el mejor programa para reproducir cualquier tipo de video en Linux (incluyendo VCD), es el mplayer.