A partition editor to adjust partition boundaries for a different hard drive, or the same one with different geometry, or to adjust partition sizes within the same hard drive. A GUI would probably be a good idea here. On the other tentacle, the FSF's parted looks like it will fill part of the bill. It does re-size existing partitions, but with restrictions.
make.fdisk currently spits out one script. Separate out the mount commands to another script, so you can run make.dev.hda, then reboot to do some other mischief, like build a partition for some exotic OS I've never heard of, or run parted, then reboot to tomsrtbt, mount all the Linux partitions, and continue.
Since tomsrtbt supports bzip2, convert the scripts to use bzip2, and see if there is a noticeable reduction in the first stage data saved.
make.fdisk currently only recognizes some FAT partitions, not all. Add code to make.fdisk to recognize others and make appropriate instructions to rebuild them in the output files.
For FAT12 or FAT16 partitions we do not format, write zeros into the partition so that Mess-DOS 6.x does not get confused. See the notes on fdisk for an explanation of the problem.
Make a script for putting ext2 file systems on ZIP® disks.
Translations into other (human) languages.
Find out how loadlin or similar programs affect this process.
Changes for GRUB
Change the scripts to use a CD-ROM. A CD-ROM that would boot to tomsrtbt, with the first stage restore data on the rest of it, would be just the ticket.