"It's not about you, it's about them."
This is a good thing to remember whenever you feel like this. The vast majority of the time, what people do and say doesn't have much to do with you personally, and is instead just a result of them doing the best they can with the knowledge and abilities they have.
In this case, think about it from the acceptance committee's point of view. They have a presumably large stack of applicants, and only a few openings. "Openings" in graduate school are created when a professor is fairly confident that they can secure funding for a student for at least 5 or 6 years. It's kind of a catch-22 in that you need the students to do work to get the funding, but you need the funding to get the students. So there is always an element of risk where you think you will be able to provide support and that you will be able to find students to work on your project, but you aren't completely sure.
When application season starts, the department tries to predict how many funded positions there will be, given the number of awarded or likely-to-be-awarded grants, teaching assistant positions, and fellowships provided by the school. They then try to select a number of students to accept that is a little larger than that (because not everyone who is accepted will end up joining), but not too large.
Given these constraints, you can see how important it is to correctly guess which of your applicants will have the skills needed to succeed in the program and also have interest in one or more of the available funded (or likely to be funded) projects. How do you do this, given only GRE scores, transcripts, reference letters, a CV, and a statement of interest?
When you need to quickly cut down a large stack of applicants to a much smaller number, the easiest way is to filter based on some pre-established criteria. GRE and GPA are probably not the best measure of potential success as a researcher, but they are a proxy measure for the basic skills you need as well as an indicator of an ability to do what you are supposed to do when you are supposed to do it. For those reasons, they are often used as a first-pass filter to reject applicants. Most professors I have talked to know that in doing this, they are potentially rejecting people who would have made very capable researchers, but this is a game of odds - you are trying to predict how likely a person is to succeed without knowing much about them. A pool of students with high GPA and GRE scores is more likely to contain a higher number of successful researchers than a pool with low scores.
There is no way of knowing (unless they tell you) whether you were rejected because of this filter or not. Usually a department will tell you up front what the range of GPA and GRE scores that they accept is, so that applicants don't waste their time. Since you got in with an NSF fellowship, let's assume you were at least past the minimum.
Now the committee has a smaller but still too-large pool of applicants that they are betting has a higher chance of success. The next step is to go through and find the best candidates. One way to predict future research success is if you have a record of previous success - that's why undergraduate research experience is so valuable for a graduate school application. You said you have that - so as long as you had a good letter of recommendation from your PI, that probably helped you. Letters of recommendation carry a lot of weight at this point, because they are the only way that the committee can get a sense of what it is like to work with you. A lot of very capable people don't have great letters of recommendation because they didn't interact much with their professors. Even if you did extremely well in a given class, if the professor doesn't know you very well, they can't say much besides "this student made good grades."
The last thing they look at is your statement of interest. Remember - they are trying to match interested and capable students to funded positions. If your statement of interest doesn't communicate a strong match to one or more of the areas that have openings, then they might not want to risk accepting you over someone else who is interested.
Notice that in all of these scenarios, at no point were people making a judgement about how "good" you are as a researcher - they were instead making a bet about whether or not you would be more likely to succeed in their research program compared to other candidates. For whatever reason, they decided that based on the information they had, the other candidates had a higher chance of success.
Remember that the two constraints which made estimating these odds so important were a limited number of funded research positions and the fact that not every student is interested in every project. Once you secured NSF funding, you changed three very important things:
1) You created a new funded position
2) You proved that you were interested in working on that project
3) You got the equivalent of a strong letter of reference from the NSF
Once you add these things to your application, you are practically eliminating risk for the department. As long as there is a professor who has the capacity to advise you and an interest in the project, you would be very likely to get into any school.
Thinking about it this way, hopefully it is clear that it was not that they thought you weren't good enough before, but now that you are bringing in money you are. It is more likely that you were too risky a bet, and now you are not. In that sense, it wasn't that you were not good enough, but that your application was not convincing enough. Those are two very different things, and I believe that most professors understand that. The application and the NSF fellowship are just two different types of keys letting you into the same door. Once you are through the door, you will be judged by how well you do in your classes and (more so) by your research work.
