Este é o comportamento "normal" na medida em que os servidores onde você chama "yum update" mantêm um cache dos pacotes disponíveis no repositório. Quando você chama "yum clean all", este cache é deletado, e o servidor precisa perguntar ao repo novamente para uma lista de pacotes disponíveis - incluindo o pacote recém-adicionado.
O que realmente acontece
- você adiciona um novo pacote ao repositório na máquina A
- você chama createrepo - as informações do repositório são atualizadas
- você pula para o servidor B onde o repositório da máquina A está incluído
- você chama "yum update" em B - a última execução do yum não foi há muito tempo, portanto yum não (!) conecta-se a A, mas apenas verifica o cache local; já que o cache local é, digamos, algumas horas, seu novo pacote não está listado lá
- agora, já que você está chateado, você chama "yum clean all" em B [você também pode esperar um pouco]
- todo o cache é excluído em B
- outra chamada de "yum update" em B força B a se conectar ao servidor, puxando todos os dados atuais - e assim podendo ver seu novo pacote