Eu tive o mesmo problema no Ubuntu 12.04. Mudar o aplicativo padrão de vídeo para o VLC não tem efeito, enquanto para os outros (web, correio, música, etc ...) ele funciona. Parece que há um bug.
Uma solução rápida:
Abra defaults.list com
gksudo gedit /usr/share/applications/defaults.list
Pesquise totem.desktop
e substitua ALL por vlc.desktop
.
Salve, feche e ... aproveite!