It appears that the issue is with trying to update grub:
Searching for GRUB installation directory ... found: /boot/grub
warning: grub-probe can't find drive for /dev/sda1.
grub-probe: error: Cannot find a GRUB drive for /dev/sda1. Check your device.map.
User postinst hook script [update-grub] exited with value 1
dpkg: error processing linux-image-2.6.26-1-amd64 (--configure):
subprocess post-installation script returned error exit status 1
This is caused when grub tries to read your
device.map file and fails to find some of the mappings. Fortunately, assuming this is just a borked config file, it can easily be regenerated.
cp /boot/grub/device.map /boot/grub/device.map.bak
Future updates should now go more smoothly. Hope this fixes your problem!
EDIT: Still empty? You have two options (at least, in this specific case):
Add the device manually to
/boot/grub/device.map; it should look like:
Force grub to recheck the drives.
grub-install --recheck /dev/sda