When ppc64-utils became an empty package, its set of files was moved to other packages, such as powerpc-utils. The /usr/bin/mkzimage script got dropped along the way but is still needed. Please add it to powerpc-utils.
Why's it needed? What does it do that the standard 'wrapper' script from the kernel (which we ship in the kernel-bootwrapper package) can't do?
David, thank you for pointing me in the right direction. After a couple tweaks in mk-images.ppc, I was able to get anaconda to build the netboot image using kernel-bootwrapper.
Er, wasn't anaconda already doing that? The images/netboot/ directory of the install image has netboot images in Fedora 11 and in rawhide...
https://www.redhat.com/archives/anaconda-devel-list/2009-September/msg00418.html contains the patch to anaconda that I needed to get netboot images on ppc64. The paths in anaconda worked for ppc but not ppc64.