Até onde eu sei, os mantenedores do upstream ocasionalmente estragam as dependências dos pacotes. Isso pode ser o que aconteceu aqui. Considere arquivar um bug no launchpad e, caso contrário, apenas espere que ele seja corrigido. Enquanto isso, você poderia tentar usar o smplayer, que eu pessoalmente prefiro vlc.