Quando o CD está danificado ou mal-gravado, a instalação fica com defeito, e dá esse tipo de problema.
Se não tiver instalado muita coisa na máquina, tente reinstalá-la, com uma mídia testada.
zekkerj,
Quando o problema é a mídia (no caso, algum pacote corrompido), o usuário é avisado durante a instalação de que o respectivo pacote está corrompido (através de uma checagem de hash/MD5 inclusa em todos as mídias do Ubuntu). Se tivesse sido algo da instalação, o usuário seria avisado de qualquer forma (hoje em dia, o debugging do Ubuntu está muito bom).
Estou com o mesmo problema e garanto a vocês que não é específico de placa de vídeo, nem do fato da instalação ter sido feita por atualização ou da forma "limpa". Não é vídeo, porque no meu trabalho utilizo uma placa de vídeo Nvidia (onboard, nForce N430) e não tive problema (aqui no fórum, tem pessoas com a mesma placa e outras com problema), no meu notebook (com vídeo SiS) apresentou problemas e no meu netbook (com vídeo Intel) não apresentou; não é o player de vídeo (testei com vários, incluindo Totem e VLC); testei com outra interface e também apresentou problemas. Entretanto, abrindo pelo console, é possível observar algumas coisas interessantes.
O que pude observar é que quando abrimos o player via console, o VLC por exemplo, podemos ver que existem alguns retornos de erro como "Warning: call to rand()". São só "warnings" (avisos), mas significa que algo está fora do padrão; o "randr" é o programa responsável pela troca de resolução no novo Xorg (das versões mais novas para cá), logo, dá para deduzir que é alguma chamada relativa ao programa citado que está com problema, ou mesmo o próprio programa está com um bug crítico (e acredito que seja a nível mundial, o que deve acelerar a correção). Se não for ele, provavelmente, é alguma biblioteca com problemas.
Sugiro então que fiquemos de olho em atualizações para bibliotecas, para o Xorg (para o servidor mesmo, não para os drivers) e/ou para os players.
Espero ter ajudado.
