Consider that, ideally, PhD programs take 5 years, and the final year is spent on (a) writing the dissertation, and (b) applying for jobs. This means that NSF graduate fellows may have as little as one year in which to get some teaching experience.
Presumably, NSF was thinking one of three things:
1) They're trying to make it harder for their fellows to get jobs at universities that care about teaching.
2) They honestly don't believe teaching experience is important.
3) They weren't thinking at all.
I'm curious what will happen at universities that require all students to teach, regardless of whether they have outside fellowships or not. Will they change that rule, or will they forbid students to have NSF fellowships. Given the current financial situation, I'm guessing they'll go with the former, but it's hard to say.
*The exact NDSEG rule is that your total income for any year should be no more than $5,000 in addition to the fellowship itself. Depending on the university, this can be less than what one would get paid for teaching a single class.