How do I stop feeling unwelcome in my department?
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.