Finalmente consegui um vídeo em 1080p para rodar e testar, e aqui na minha máquina ( AMD Phenom 9600B - Geforce 6150LE) o vídeo, mesmo demorando pra iniciar (~ 7 seg.) rodou "liso" no VLC.
No seu caso específico, acredito que seja provavelmente um problema de driver, má configuração ou alguma opção ativada não corretamente, a minha placa de vídeo é integrada à placa-mãe, e é bem ruinzinha, mas mesmo assim conseguiu executar o vídeo corretamente, mesmo com o Compiz ativado, aliás isso é um detalhe que eu esqueci de sugerir, experimente também desativar os efeitos 3D para ver se há alguma melhora, paralelo a isto, experimente nas preferências do VLC, alterar o driver de saída de vídeo (OpenGL, X11, XVideo, etc.)