Você está usando o Ubuntu ou o Kubuntu?
Pergunto isso por que para o Kubuntu, ou melhor, para o linux com kde4 como o protetor de tela ativado, o monitor parece piscar de vez em quando, mas pelo que entendi seu erro é outro mais relacionado ao vídeo e não ao monitor. A solução para o monitor ficar piscando no kde4 foi desativar o protetor de tela.
Se não é problema de falta de codecs, então deve ser algo relacionado a sua placa gráfica mal configurada para o linux, só posso pensar isso.
Se você usa aqueles efeitos do compiz-fusion, veja se desativando eles o problema se resolve ou continua.