This bug still exists in Lucid; I've had it on two separate Lucid Server VMs (the first is i386 running under VMware Server 1.x/RHEL4; the second is x86_64 running under KVM/Karmic)

The problem was triggered by a simple upgrade, which pulled in a new versions of grub-common and grub-pc. Here's the full transcript of when it happened the second time:

$ sudo apt-get dist-upgrade
Reading package lists... Done
Building dependency tree       
Reading state information... Done
Calculating upgrade... Done
The following NEW packages will be installed
  linux-image-2.6.32-26-virtual
The following packages will be upgraded:
  grub-common grub-pc linux-image-virtual linux-virtual
4 upgraded, 1 newly installed, 0 to remove and 0 not upgraded.
Need to get 14.7MB of archives.
After this operation, 36.0MB of additional disk space will be used.
Do you want to continue [Y/n]? y
Get: 1 http://gb.archive.ubuntu.com/ubuntu/ lucid-updates/main linux-image-2.6.32-26-virtual 2.6.32-26.47 [12.5MB]
Get: 2 http://gb.archive.ubuntu.com/ubuntu/ lucid-updates/main grub-pc 1.98-1ubuntu8 [650kB]
Get: 3 http://gb.archive.ubuntu.com/ubuntu/ lucid-updates/main grub-common 1.98-1ubuntu8 [1,540kB]
Get: 4 http://gb.archive.ubuntu.com/ubuntu/ lucid-updates/main linux-virtual 2.6.32.26.28 [4,150B]
Get: 5 http://gb.archive.ubuntu.com/ubuntu/ lucid-updates/main linux-image-virtual 2.6.32.26.28 [4,160B]
Fetched 14.7MB in 19s (758kB/s)                                                
Preconfiguring packages ...
Selecting previously deselected package linux-image-2.6.32-26-virtual.
(Reading database ... 17623 files and directories currently installed.)
Unpacking linux-image-2.6.32-26-virtual (from .../linux-image-2.6.32-26-virtual_2.6.32-26.47_amd64.deb) ...
Done.
Preparing to replace grub-pc 1.98-1ubuntu7 (using .../grub-pc_1.98-1ubuntu8_amd64.deb) ...
Unpacking replacement grub-pc ...
Preparing to replace grub-common 1.98-1ubuntu7 (using .../grub-common_1.98-1ubuntu8_amd64.deb) ...
Unpacking replacement grub-common ...
Preparing to replace linux-virtual 2.6.32.25.27 (using .../linux-virtual_2.6.32.26.28_amd64.deb) ...
Unpacking replacement linux-virtual ...
Preparing to replace linux-image-virtual 2.6.32.25.27 (using .../linux-image-virtual_2.6.32.26.28_amd64.deb) ...
Unpacking replacement linux-image-virtual ...
Processing triggers for man-db ...
Processing triggers for ureadahead ...
ureadahead will be reprofiled on next reboot
Setting up linux-image-2.6.32-26-virtual (2.6.32-26.47) ...
Running depmod.
update-initramfs: Generating /boot/initrd.img-2.6.32-26-server
Running postinst hook script /usr/sbin/update-grub.
Generating grub.cfg ...
Found linux image: /boot/vmlinuz-2.6.32-26-server
Found initrd image: /boot/initrd.img-2.6.32-26-server
Found linux image: /boot/vmlinuz-2.6.32-25-server
Found initrd image: /boot/initrd.img-2.6.32-25-server
Found linux image: /boot/vmlinuz-2.6.32-24-server
Found initrd image: /boot/initrd.img-2.6.32-24-server
done

Setting up grub-common (1.98-1ubuntu8) ...

Setting up grub-pc (1.98-1ubuntu8) ...

***
At this point, the dialog box came up:
--------------------------------------------------------------
You chose not to install GRUB to any device. If you continue, the boot
loader may not be properly configured
... blah blah blah ...
Continue without installing GRUB?

Selecting <No> - just redisplays the same screen.
Selecting <Yes> - is the only possible getout
--------------------------------------------------------------

Generating grub.cfg ...
Found linux image: /boot/vmlinuz-2.6.32-26-server
Found initrd image: /boot/initrd.img-2.6.32-26-server
Found linux image: /boot/vmlinuz-2.6.32-25-server
Found initrd image: /boot/initrd.img-2.6.32-25-server
Found linux image: /boot/vmlinuz-2.6.32-24-server
Found initrd image: /boot/initrd.img-2.6.32-24-server
done

Setting up linux-image-virtual (2.6.32.26.28) ...
Setting up linux-virtual (2.6.32.26.28) ...

***
After this, I can reproduce the problem at will by typing "sudo dpkg-reconfigure grub-pc". It prompts me first for the command line and the default command line, then goes into the same dialog loop unless I say "Yes" to "Continue installing without GRUB"

These two VMs *do* still boot up successfully, but it's worrying that in future they may not.