For the past few hours I have been battling with Virtualbox to install Hardy as a Guest. It would always get to the end and then provide an error that Grub could not be installed. Fine, let me try Lilo, same thing. Well, I figured out the problem. I had been setting the Virtualbox hard drive setting for the guest to dynamic, which would make the drive allocation expand if and when needed. I decided to give it a static size, which means if I give it 6GB of space it will setup 6GB of space instead of expanding when necessary. Well, I went ahead and started the install and it just finished, had no problems installing Grub this time around.
Moral of the story, if you experience this Grub installation issue on Virtualbox, use a static (bottom radio button) size for the drive allocation when creating a new guest.