So I've figured out the issue (finally).  Apparently, the optional grub stage 1.5 is stored in the normally unused space between the mbr and the start of the first partition.  The image I chose to use for my testing did use this grub stage 1.5 (I think fedora doesn't by default though), and of course, I wasn't capturing that data in my images (I only recorded mbr, partition table, and partition contents)

So I've modified my script to capture three things now.
1) the first 63 sectors (63 * 512 bytes) of the hard drive.  This includes the mbr and all space before the first partition, which starts on sector 63 for all machines I've looked at.  I'm assuming this is always the case (is this a valid assumption?)

2) The output from sfdisk -d, to capture extended partitions

3) A full image of each partition using dd.

I've tested this and it seems to work perfectly.  I've attached the most recent version of my kickstart file which includes the script.

The next step at this point, and correct me if I'm wrong, is to get partimage or some other utility to stand in for dd.
I was taking a look at partimage-ng, which looks like a full rewrite of partimage that looks promising.  It also has built in capability to fall back to a dd like copy for unknown filesystems.

Oh, and also:  Unless partimage somehow captures that data automatically, as far as I can tell XCat's imaging functionality has the same issue.  I figure we just hadn't run into it yet because all the Red Hat based images we have don't use the grub stage 1.5.

-Andrew Brown