Yum finds package in search but can't find it to install

I got this issue on an FC8 server where if I search for something in yum, it finds the packages I am searching for but then when I go to install the package it says its not there...?

[hamstar@tankian ~]$ yum search pecl
php-pecl-apc.i386 : APC caches and optimizes PHP intermediate code

[hamstar@tankian ~]$ sudo yum install php-pecl-apc.i386
Setting up Install Process
Parsing package install arguments
No package php-pecl-apc.i386 available.
Nothing to do

[hamstar@tankian ~]$ sudo yum install php-pecl-apc
Setting up Install Process
Parsing package install arguments
No package php-pecl-apc available.
Nothing to do

wtf?

EDIT: Yum update shows this:

[hamstar@tankian ~]$ sudo yum update
Setting up Update Process
No Packages marked for Update

EDIT: I also tried this and tried it all again with no luck:

[hamstar@tankian ~]$ sudo yum clean all
Cleaning up Everything

EDIT: So i just realized this package is installed, but replacing the package name for pyqt (and variations of) which is not installed gives the same results. Here is the output for a package that is already installed on my other FC8 server.

[root@dolmayan ~]# yum install php
Setting up Install Process
Parsing package install arguments
Package php - 5.2.4-3.i386 is already installed.
Nothing to do

RESOLUTION
In Alex's comment down there he said go to this fedora wiki page so I did and followed the commands:

wget http://kojipkgs.fedoraproject.org/packages/fedora-release/8/6.transition/data/signed/4f2a6fd2/noarch/fedora-release-8-6.transition.noarch.rpm
su -c 'rpm -Uvh fedora-release-8-6.transition.noarch.rpm'

Got the key from here emptied the old gpg key and pasted the new one into it.

su -c 'echo > /etc/pki/rpm-gpg/RPM-GPG-KEY-fedora-8-and-9
sudo vi /etc/pki/rpm-gpg/RPM-GPG-KEY-fedora-8-and-9

Then I ran:

su -c 'rpm --import /etc/pki/rpm-gpg/RPM-GPG-KEY-fedora-8-and-9'

Done!