I took a peak at a few of the mirrors... It looks like some of them are dropping everything below FC6. When you yum, it gets assigned a random mirror, which might not have the packages for FC4.
Go to /etc/yum.repos.d/ and look for a file that has "extras" in the name. I use F8, so I don't have extras anymore, so I don't know the exact name. Edit that file. It will look similar to this...
Code:
[fedora]
name=Fedora $releasever - $basearch
failovermethod=priority
#baseurl=http://download.fedora.redhat.com/pub/fedora/linux/releases/$releasever/Everything/$basearch/os/
mirrorlist=http://mirrors.fedoraproject.org/mirrorlist?repo=fedora-$releasever&arch=$basearch
enabled=1
gpgcheck=1
gpgkey=file:///etc/pki/rpm-gpg/RPM-GPG-KEY-fedora file:///etc/pki/rpm-gpg/RPM-GPG-KEY
[fedora-debuginfo]
name=Fedora $releasever - $basearch - Debug
failovermethod=priority
#baseurl=http://download.fedora.redhat.com/pub/fedora/linux/releases/$releasever/Everything/$basearch/debug/
mirrorlist=http://mirrors.fedoraproject.org/mirrorlist?repo=fedora-debug-$releasever&arch=$basearch
enabled=0
gpgcheck=1
gpgkey=file:///etc/pki/rpm-gpg/RPM-GPG-KEY-fedora file:///etc/pki/rpm-gpg/RPM-GPG-KEY
[fedora-source]
name=Fedora $releasever - Source
failovermethod=priority
#baseurl=http://download.fedora.redhat.com/pub/fedora/linux/releases/$releasever/Everything/source/SRPMS/
mirrorlist=http://mirrors.fedoraproject.org/mirrorlist?repo=fedora-source-$releasever&arch=$basearch
enabled=0
gpgcheck=1
gpgkey=file:///etc/pki/rpm-gpg/RPM-GPG-KEY-fedora file:///etc/pki/rpm-gpg/RPM-GPG-KEY
In the first section, take the # off the beginning of the baseurl= line and add it to the mirrorlist= line. That will uncomment the first line and comment-out the second line. This way, you won't request a mirror server, and only go straight to the redhat server.
If you continue to have problems, do the same with the other repo files in that directory... fedora, updates, whatever-they-are.