$ sudo aptitude purge grub-efi-amd64 grub-pc
The following packages will be REMOVED:
  grub-efi-amd64{p} grub-pc{p}
0 packages upgraded, 0 newly installed, 2 to remove and 10 not upgraded.
Need to get 0B of archives. After unpacking 0B will be used.
Do you want to continue? [Y/n/?]
(Reading database ... 136342 files and directories currently installed.)
Removing grub-efi-amd64 ...
Purging configuration files for grub-efi-amd64 ...
ucfr: Association belongs to grub-efi-ia32, not grub-efi-amd64
ucfr: Aborting
dpkg: error processing grub-efi-amd64 (--purge):
 subprocess installed post-removal script returned error exit status 5
Removing grub-pc ...
Purging configuration files for grub-pc ...
ucfr: Association belongs to grub-efi-ia32, not grub-pc
ucfr: Aborting
dpkg: error processing grub-pc (--purge):
 subprocess installed post-removal script returned error exit status 5
Errors were encountered while processing:
 grub-efi-amd64
 grub-pc
localepurge: Disk space freed in /usr/share/locale: 0 KiB
localepurge: Disk space freed in /usr/share/man: 0 KiB
localepurge: Disk space freed in /usr/share/gnome/help: 0 KiB
localepurge: Disk space freed in /usr/share/omf: 0 KiB
localepurge: Disk space freed in /usr/share/doc/kde/HTML: 0 KiB

Total disk space freed by localepurge: 0 KiB

E: Sub-process /usr/bin/dpkg returned an error code (1)
A package failed to install.  Trying to recover:

$

What versions of grub-efi-amd64 and grub-pc were installed?  (This
information should be in /var/log/dpkg.log, if nowhere else.)

This bug sounds awfully like #574176, which I fixed in grub2
1.98+20100527-1, but if you had older versions of these packages
installed then you won't have had this fix.