Para tentar explicar como isso pode ter acontecido, parece que em algum momento você apontou seu servidor para o repositório Yum do Grupo de Desenvolvimento do PostgreSQL (PGDG), agora hospedado em link Houve algumas mudanças no repositório que podem ter quebrado sua capacidade de usá-lo. Além disso, o RedHat adicionou agora o PostgreSQL 8.4 ao seu próprio conjunto de pacotes - você costumava ser capaz de obter apenas 8.1 deles - então, pode ser que o conflito tenha sido introduzido.
Se você tiver mais problemas aqui, o PostgreSQL Yum Howto pode ajudar você a ter uma ideia de onde os arquivos envolvidos aqui estão em, e como devem ser.