Well I seem to be having the same problem with my FC4.
I've got the most resent kernel
[root@nts]# uname -r
I have also resently installed kernel-devel through yum
after doing this the install still gave an error similar to the first post.
So I downloaded the 2.6.12-1.1398_FC4-ppc.src.rpm from download.fedora.redhat.com
In order for the installer to find my source I ran it with the --kernel-source-path
sh NVIDIA-Linux-x86-1.0-7676-pkg1.run --kernel-source-path /usr/src/kernels/2.6.12-1.1398_FC4-ppc/
The has gotten me past the errors that naad was getting but just simply given me the error
ERROR: Unable to build the NVIDIA kernel module.
ERROR: Installation has failed. Please see the file
'/var/log/nvidia-installer.log' for details. You may find suggestions
on fixing installation problems in the README available on the Linux
driver download page at www.nvidia.com