Sorry, I have to ask: did you do it as root?
fdisk should reside in /sbin, if I recall correctly...
If not, you can get it from the redhat site. Here is a list of all the files provided by the package containing fdisk:
http://www.redhat.com/swr/i386/util-...2.i386_fl.html
(I believe this is only for ext2, so if you have another filesystem in use, I'm out of ideas). If you can, use the util-linux package on your install disks.
I haven't used rpm in a while, so I don't remember if you can just extract the file you want, as opposed to reinstalling a large portion of your important utilities...