If you download and run the boot info script from the following location and attach the RESULTS.txt and your /etc/default/grub contents I can take a look.
http://bootinfoscript.sourceforge.net
Added: I just loaded up Lucid in a VM and GC worked as expected. By looking at your scripts we may be able to find out what is different on your machine.
Bookmarks