Well, all you can really do is to clench your teeth and work. It may take a few months to a few years before you get to the point when you'll be certain that you are worth something and then a few more years before you finally realize that your brain is ridiculously slow, blind, and malfunctioning and you slide into the normal stable depression state any working mathematician lives in (I'm not so sure about other sciences but do not see why it should be any different there) :-).
The point is that what people see is what you produce: above a certain level, you are judged by your output, not by your working habits and other "test" criteria. On the other hand, above the same level, you spend the rest of your life walking a narrow path between being dissatisfied with yourself to the extent of quitting and being not enough dissatisfied with yourself to strive for improvement. You just have veered too much to the left, that's all.
As to the graduate coordinator, the second phrase puzzles me way more than the first (the first one makes sense and I can easily say it myself when I see that the things just do not work out after a few years, the second one looks more like a lame excuse for saying the first). Well, who cares? If you can do something, you'll see it yourself. If not, some other people will take care of showing it to you.
As to the feeling of "not belonging", the internet won't help here. Either talk to your psychiatrist (if you believe in psychiatry), of just take time out and do some physical activities on fresh air.
Above all, remember that we have all been there at the beginning of our careers: stupid worthless students struggling with the most routine homework and learning that the first problem of solving which they were proud was actually put on the test just to console those who cannot figure out anything interesting.
So, veer a bit to the right (not too much though) and continue walking forward (and, of course, as it was said in the final song of Monty Python's "Life of Brian", always look at the bright side of life...)