Amigo... o yum SEMPRE foi lento... no mundo Fedora... até hoje sonho com alguma solução que seja mais eficaz pra ele... 
Tive o mesmo problema que você... dai um limpei o cache e resolveu em partes:

# yum clean
# yum clean all

Usei esses comandos, limpei o cache, e o yum ficou um pouco mais rápido... mas lembre-se ele é SEMPRE lento, infelizmente... e ainda temos a lentidão da net pra somar... então já viu né... paciência...

Valeuzzz

PS: Instale o easylife (http://www.easylifeproject.org/) ele automatiza muita coisa no Fedora, principalmente os codecs multimídia e e adiciona outro repositório no yum... isso também ajudou um pouco mais na velocidade do meu yum.