Quando eu estava inicialmente configurando minhas caixas do CentOS, tive muitos problemas semelhantes.
As reposições RHEL e CentOS podem ser usadas de forma intercambiável. Com um grau de cuidado, até mesmo os repos RHEL 5 podem ser usados. Quando se trata de usar esses repositórios, você precisa usar apenas um único repositório externo - RPMForge, EPEL, etc. Repositórios de mixagem criam um grande problema. Também não se esqueça de usar o plugin yum-priorties.
Quando se trata dos pacotes listados com dependências quebradas, eles geralmente podem ser removidos e reinstalados para corrigir problemas de dependência. Apenas certifique-se de fazer uma lista de pacotes impactados. Isto é especialmente verdadeiro para o VLC - havia apenas cerca de 4 ou 5 pacotes impactados na última vez que eu precisei fazer isso.
Meu repositório preferido é o RPMForge. link
Se você tem misturado repositórios, sugiro que você remova todos os pacotes de repositórios de terceiros e comece novamente. Isso pode ser feito com a reinstalação do SO ou manualmente rastreando os pacotes . Se você não usou prioridades do yum para começar, seu sistema provavelmente está muito quebrado e uma reinstalação seria a melhor solução.