Ocorreu o mesmo comigo, instalei o ubuntu-restricted-extras e estava utilizando VLC como player, rodando os vídeos normalmente.
No dia seguinte a reprodução estava ocorrendo de forma lenta, decidi reinstalar o Ubuntu 9.04, poís havia feito o particionamento errado (primeira vez no ubuntu).
Instalei o ubuntu-restricted-extras e os vídeos estavam rodando, mas no dia seguinte, quando religuei o computador ocorreu o mesmo problema, reinstalei o ubuntu-restricted-extras e instalei o VLC, não resolveu.
como faço para resolver?