In my continued travels on the subject of Debian Packages, I came across a discussion of checkinstall. Basically, the high and low of it is that checkinstall is quick and easy--but the packages will not necessarily work all that well in a clean room environment. This combined with the fact that the paths in the previous package are not quite right, prompted me to build a new package "the right way". It is now available.
Before I talk about the solution, I wanted to mention a couple of things that researching this problem brought into greater perspective for me.
That out of the way, here is what I did: First, I downloaded and extracted the source. Then I cd'd into the base source directory. Then I ran:
$ dh_make -n -e my-email@my-domain.dom
This command generates default build scripts for the Debian package (note: you will need to ensure that the package for dh_make is installed). The next step is to edit the control file. This will, by default, be created under debian/control. The main changes needed are to the description and to the dependencies. The documentation on the specifics can be found here. As it is relatively straight forward I will not go into detail on it here. Once you have finished with that, you would need to edit the various rules in the rules file. If, however, your software is fairly standard automake
then you probably don't need to do anything. If, on the other hand, you were using NAnt, Ant, HMake, or some other custom build system you would have to modify the rules file to build properly. After all of this is squared away, simply run
$ fakeroot debian/rules binary
If the previous step was completed correctly, dh_make will spit a shiny new Debian package out
in the parent directory. A good old fashioned dpkg run and the package will install on your system.