Vale> Как это побороть?
Попробуй на каталоге правой кнопкой -> Открывать в программе -> Другое приложение ...
Если там нет - то тупо поищи vlc в gconf-editor
Не найдёшь - забэкапь и грохни ~/.gconf, перелогинься и посмотри результат. Пройдёт - дальше в настройках gnome искать нужно. Нет - что-то более общесистемное, м.б. xdg-что-то...