My machine has 64-bit support so I figured I'd give it a go, installing a 64-bit debian on one partition and keeping the working i386 debian on another.

So I installed the amd64 version (using it now), but now grub only lists this one when I boot up. It also lists Ubuntu, which is still there on yet another partition but I can't choose between my two debians. The installer did say that both Ubuntu 6.06 and Debian 4.0 were detected.

I didn't erase the old partition, it's just not showing. Is there a way to resolve this short of editing /boot/grub/menu.lst manually, so that things like the "debian automagic kernel list" when new kernels are installed are not broken?

No, but if you edit it manually as long as you add it under the ### END DEBIAN AUTOMAGIC KERNELS LIST it will not remove them.