There were other holes that had to be there too: the handler code was incorrectly dereferencing a pointer before the check for null (that's a real bug), and the compiler was optimizing out the null pointer test in the same function (a really, really subtle interaction that no one expected) that would have detected the attack and returned an error instead.
It's a perfect storm of coincidence, basically. There's nothing the NSA could have done to predict this, and the SELinux part is only a small piece. And in any case, the security policy bug isn't even in the NSA's SELinux code at all, it's in the way the kernel sets defaults for its security policies for any security module. In principle, app-armor would be vulnerable to the same issue (not sure if it is or not to this one specifically).