Используйте aptitude, иногда более разумную альтернативу apt-get.
Если вы запустите sudo aptitude remove vlc, он обнаружит возможные конфликты, которые приведут к удалению vlc, и предложит удалить все те другие «скрытые» зависимости, которые apt-get пропустили при первом запуске.
Если вы еще не установили aptitude, это можно сделать с помощью sudo apt-get install aptitude.