O mesmo problema aqui. Estou usando o NVidia uma aceleração de hardware funciona bem com o mplayer.
Executar o vlc -vvv mostra que o problema parece estar relacionado ao avcodec e ao multithreading:
305 [0xb7049a70] avcodec decoder debug: allowing 4 thread(s) for decoding
306 [0xb7049a70] avcodec decoder warning: threaded frame decoding is not compatible with ffmpeg-hw, disabled
307 [0xb7049a70] avcodec decoder debug: ffmpeg codec (H264 - MPEG-4 AVC (part 10)) started
Uma compilação personalizada de fontes VLC ("instalar dependências de compilação" - > ./bootstrap - > ./configure - > make - > sudo make install) funciona bem.