Oi, sou iniciante no linux e tava com esse problema e resolvi aqui no meu pc desse modo:
Como uso o VLC ja tinha ido em ferramentas - preferências - vídeo - saída de vídeo: saída de vídeo do X11 (XCB) - salvar
mesmo assim continuou do mesmo jeito e voltei para a saída de vídeo padrão
Em um tópico encontrei esses passos:
Atl + F2
gstreamer-properties
Na aba vídeo selecionar o plug-in: X window system (sem XV)
ainda continuava do mesmo jeito mas deixei com essa configuração e refiz os passos anteriores no VLC selecionando a saída de vídeo do X11 (XCB) e o vídeo agora roda normal não só no VLC mas também no programa padrão do ubuntu 11.04 que também não rodava.
espero que consiga com esses passos, valeu!