Can't boot, no grub, "alloc magic is broken"

I cannot boot into GRUB. I see this:

Alloc magic is broken at XXXXXX Press any key

but when I do nothing happens. Holding shift doesn't do anything either.

The last time I could use my machine I changed stuff in /etc/grub.d, but I chrooted into the system, reverted everything and successfully ran update-grub.

What can I try?

If anyone wondering: Ubuntu 12.04.1, Installation media was (I guess) 11.10, it's an i5-first generation kernel, 4GB RAM, memtest was okay.

A Boot-Repair Live USB can be used to repair Grub. You can download the ISO from the Ubuntu Wiki. Then, use Unetbootin to create a Live USB from the ISO file you downloaded. After you boot from the USB, the Boot Repair utility will pop up. Just click on the Recommended Repair button, and Boot-Repair will repair Grub for you.

This is not a software issue, The alloc magic broken error is a result of bad memory chips.