Läuft VLC mit VAAPI besser?
vlc --avcodec-hw=vaapi Beispiel.mp4
GVFS-WARNING **: can't init metadata tree /home/xxx/.local/share/gvfs-metadata/root: open: Keine Berechtigung
Durch die Unity auf Gnome Umstellung hat es vermutlich bei dir "gekracht". GVFS ist für den Datenfluß verantwortlich, es liegt also eventuell gar nicht an den Playern.
Läuft ein
sudo apt-get autoclean sudo apt-get autoremove sudo apt-get update
problemlos durch?
Vorbeugend würde ich auch mal die Rechte im home korrigieren. (siehe Wiki)
Einen frischen Nutzer testen wäre auch mal interessant.