That sounds like a personal decision you will have to answer on your own, but here are just a few things to consider as you make your decision.
Have you already obtained a Master's degree? If not, you could finish that and leave for the PhD program elsewhere with fewer problems.
It is okay to change advisers if one is not working out. You don't necessarily need to leave the school you are at to do that.
If you are comfortable with it, talk with your department chair. Explain what is happening, and get his/her advice. Another alternative would be the graduate committee chair. They want you to succeed, and can offer advice on ways to change advisorsadvisers.
It is a normal part of research to find out others have done the work before you. Some options include: generalizing what was done, researching similar but different questions, communicating with the authors of those other papers about other research avenues, etc...
Whether or not your adviser will be angry with you depends a lot on how you deal with this situation, and what your adviser is like. My advice: be honest and talk with your adviser.
