Emita o comando: yum clean all
Isso acontece porque o yum não conseguiu a nova lista de pacotes do servidor de repo. Geralmente é precedido por uma mensagem
Yum Error: "Not using downloaded repomd.xml because it is older than what we have"
Limpar o cache yum irá forçá-lo a baixar novamente a lista de pacotes e, consequentemente, reconhecer os pacotes.
Se isso não ajudar, você também pode tentar limpar um pouco de cache em rm /var/cache/yum/.....