Oi Rômulo;
então cara estou com um problema parecido com vídeos, mas só (acho que só) com vídeos tipo wmv. Quais tipos de vídeo vc está tentando ver?
Pra remover codecs acesse Sistema->Administração->Gerenciador de Pacotes Synaptic, mas não é uma boa idéia na minha opinião. Além de ser trabalhosa a reinstalação de codecs um por um dificilmente resolveria algo =)
Dê mais informações, o reprodutor de vídeo não dá nenhuma mensagem de erro ou coisa assim? Qualquer coisa nesse sentido ajuda.
Até =)