Thanks. I just got rejected from NSF yesterday too and was trying to forget about it! Maybe next year. It seems there are three people on the results page from last year that received this message and later got the fellowship, but most are denied.
I did. I have also never taken a subject test and only took the GRE once. I contacted ETS and they said that my registration number was correct. I emailed the NDSEG people and they told me that the problem is that I changed my name since I took the test. I went back in and changed my name for my GRE scores and that fixed it.
I put a header on both of my statements. I haven't been disqualified (yet at least). I copied my header style directly from a friend who applied last year and won the fellowship.