As GRUB uses nested functions, it needs an executable stack.

Using these kernel options will give your grub-mkdevicemap, grub-setup and grub-probe unusable:

CONFIG_PAX_PAGEEXEC=Y
CONFIG_PAX_SEGMEXEC=Y

There are two ways to solve this problem:

1. Disabling the exec shield:
echo 0 > /proc/sys/kernel/exec-shield
[now run boot-update]
echo 2 > /proc/sys/kernel/exec-shield

2. Setting some PAX flags on the affected binaries (requires paxctl):
paxctl -cms /sbin/grub-probe
paxctl -cms /sbin/grub-mkdevicemap
paxctl -cms /sbin/grub-setup

The following links serves as referral pages where other distro users have found the same problem:

http://bugs.debian.org/cgi-bin/bugreport.cgi?bug=503173
https://bugzilla.redhat.com/show_bug.cgi?id=731111
http://forums.grsecurity.net/viewtopic.php?f=3&t=2963