Estava com um problema no meu Fedora Core 1:

O up2date (o "Windows Update" do Fedora Core) estava me avisando de novas atualizações, mas quando eu tentava instalá-las, reclamava sempre de algumas dependências.

Até aí, nenhum problema. Mas o que estava acontecendo é que as dependências já estavam instaladas.

Então, eu tentava reinstalá-las, usando um clássico:

rpm -Uvh dependencia.rpm

Ao que o rpm respondia, avisando que o pacote já estava instalado (exemplo do perl):
[root@fabiux downloads]# rpm -Uvh perl-5.8.1-92.i386.rpm
Preparing... ########################################### [100%]
package perl-5.8.1-92 is already installed

Eu respondia com um --force, e tudo ficava bem:
[root@fabiux downloads]# rpm -Uvh --force perl-5.8.1-92.i386.rpm
Preparing... ########################################### [100%]
      1:perl ########################################### [100%]

Só que isso já estava se tornando rotina: toda vez que eu atualizava algum componente, o up2date reclamada de alguma dependência.

Então, resolvi tentar um:
[root@fabiux downloads]# rpm --rebuilddb

Pronto! Meus problemas acabaram!!

Moral da história: quando seu up2date começar a reclamar de dependências que vc tem certeza que já tem instaladas, tente um rpm --rebuilddb.