You should have upgraded release-by-release (Fedora 4 to Fedora 5, Fedora 5 to Fedora 6, etc). This can be done by using
after having installed the appropriate yum repositories. It worked for me. Googling on this topic will give you enough info.
Upgrading from Fedora 4 to Fedora 8 is quite a big step. It could work, but I haven't tested that.