O VLC é um ótimo jogador, então esse não é o problema. No entanto, você pode brincar com as configurações de vídeo.
Isso provavelmente é um problema de codec ou de hardware. Certifique-se de ter o pacote de formatos restritos instalado no Ubuntu ( link ). Se possível, você poderia postar quais codecs são usados para codificar seus vídeos? Você pode estar usando codecs antigos ou errados para decodificar seu vídeo. Resultando em sucesso apenas parcial. Meu amigo tinha um vídeo de 720p tocando muito bem em seu netbook depois de alguns ajustes no codec.
Vendo que este é um netbook, ele pode não ter toda a energia necessária para renderizar o vídeo perfeitamente. Isso resultaria em quadros perdidos e vídeo "instável". Tente reproduzir o vídeo usando o VLC em outro computador, de preferência um computador desktop. Acontece a mesma coisa?