Tim -- couple of thoughts for you:
I have one system that has no /boot/grub/device.map file, and other systems that have it. I think it must be generated only under certain conditions, as I would not delete such a system file.
Comparing your /boot/grub/grub.cfg file to a couple of mine, if f2d0e7e0-7f13-4876-8c66-75df4fbaff28 is the correct UUID for the partition where /boot is located, and if hd1/gpt7 is the correct partition, then it's not obvious why it is not booting.
Is there any chance that the BIOS drive order has changed? That would mess up the booting, for sure.
You said you ran grub-install, but I wonder if you really need to reinstall the grub-pc package from a Live CD/USB environment, and point it at the hd1/gpt7 partition where /boot is located (which must be mounted in the Live environment).
Here is the debian coverage, but it doesn't get very specific on how to reinstall grub to a particular combination of master boot record and OS (or /boot) partition:
http://debian-handbook.info/browse/squeeze/sect.config-bootloader.html