Eu estava passando exatamente pelo mesmo problema.
Mas desde que eu pensei para ter certeza de que eu não tive esse problema com o driver de vídeo linux padrão, comecei a experimentar com as configurações no Catalyst Control Center. O que eu tenho é a configuração para o Pixel Format (disponível apenas quando se usa o HDMI que eu acredito).
Agora eu configurei para Full RGB 4: 4: 4 e meus problemas se foram ... (foi YCbCr 4: 4: 2).
Espero que isso ajude os outros, já que esse problema estava me deixando louco.