Comment 2 for bug 749444

Premature comment.. ignore my last, as the option does not work as expected (menu.lst is recreated with each grub-legacy-ec2-update). Anyhow, to get this package off your system, edit the /var/lib/dpkg/info/grub-legacy-ec2.postrm script and find the following if statement,

if [ "$1" = "remove" -o "$1" = "purge" ]; then
   dpkg-divert --package grub-legacy-ec2 --remove --rename --divert \
      /usr/sbin/grub-set-default.real /usr/sbin/grub-set-default
fi

Simply change the first line,
 if [ "$1" = "remove" -o "$1" = "purge" ]; then
to
 if [ "$1" = "remove" ]; then

This removes the diversion removal step from the purge function, allowing a removal, followed by a clean purge.

#apt-get remove grub-legacy-ec2
#apt-get remove grub-legacy-ec2 --purge

..and it is gone..

root@ibm-main:/var/lib/dpkg/info# dpkg -l | grep grub
ii grub-common 1.98+20100804-5ubuntu3.1 GRand Unified Bootloader, version 2 (common files)
ii grub-pc 1.98+20100804-5ubuntu3.1 GRand Unified Bootloader, version 2 (PC/BIOS version)
root@ibm-main:/var/lib/dpkg/info#