Au vu du post de chez ubuntu, la piste non explorée (mais finalement pas non plus chez eux because réinstall avant d'avoir été creusée) était un choix incorrect de paquets (cause upgrade de distro mais apparemment pas des sources.
Vu que tu n'as pas fait cette manip, il est néanmoins possible que tu ais essayé d'installer un soft qui n'était pas fait pour cette mint là, d'où un conflit avec des dépendances soit pas encore gérées soit obsolètes, du coup ton gestionnaire voit bien que quelque chose est cassé, mais n'a pas de ressources valides pour virer ce qui est cassé puisque pas répertorié dans sa liste d'origine.
Par contre (ça m'est déjà arrivé) en virant à la hussarde tout ce qui avait trait au souci, je n'ai jamais eu de problème pour réinstaller un truc récalcitrant.
Faut croire qu'il reste donc une trace qui ne porte pas le nom de vlc dans l'ordi mais lié à l'install, peut être chercher la première cause, la dépendance non satisfaite, peut être juste une version non valide d'installée et impossible à virer par synaptic.
Au point où tu en es, tu peux encore tenter ce genre de manip.
Mais si tu penses à installer mint 18 ou 18.1, je ne crois pas que tu puisses, en live, y voir une différence de fonctionnement, elles sont trop proches, moi j'ai tenté la migration mais si je suis revenu à sarah, c'est juste une histoire de ressources système, tout fonctionnait admirablement bien, juste des freezes aléatoires qui m'ont agacés.
Je n'ai pas relevé ici où ailleurs de cas semblables avec cette mise à jour, donc c'est probablement dû à ma configuration matérielle, logicielle et..."Bidouillelle" personnelle.

Je penses aussi que c'est quand même mieux d'installer 18 que revenir à 17.3, mais rien ne t'empêchera si les 18 ne te satisfont pas d'y revenir ensuite (ça m'étonnerais) @+