How do I stop feeling unwelcome in my department? I could not find a PhD advisor and the person in charge of my PhD program suggested that I leave with a master's degree.  He said that I was good at carrying out tasks but I did not have the motivation to advance the state of the art in my field.  Some time later I found an advisor in a different department, and he seems to like me.  But I still cannot get over what the graduate coordinator said, and now I hate visiting the building because I feel I do not belong and I don't want to talk to anyone I know.  What should I do?

After I found an advisor the graduate coordinator said something like "I knew you had it in you, I just wanted to see how much you wanted it."  But I don't know if he really means it, and if he did, I think that's kind of a mean thing to do.
You mentioned that your new advisor is in a new department. So, can you cut the losses with the old department? 

But, although the comment stings, and your feelings are understandable, being able to handle it is part of completing Ph.D. To complete a Ph.D., you need (within a reason) to go against the grain, latch onto something, not listen when you are told it can't be done, and pursue it against the odds. In the process you grow a thicker skin and not let doubtful comments get and define you. 

So, it is possible that your advisor meant to test you, and see how determined you are to continue the process. I am not saying that it is the best approach, but I have seen this happen.