I had a similar problem recently where some package failed to install, which caused grub to fail as well. Switching to a console and issuing aptitude install grub did the trick.