I cannot run yum because the folder / file headers/header.info is missing in the update directory.
Is anyone aware of this?
FC4 does not use a headers directory for metadata because both yum and up2date can use the new, superior metadata format in the repodata directory. So FC4 repos do not have a headers directory.
You need to fix your yum/up2date configuration. Is your system updated from FC3? If so, look for .rpmnew files in /etc/yum.repos.d and /etc/sysconfig/rhn/
Paul.