It's possible that you really aren't capable of doing the work, and that your advisor thought about this for a long time and decided that the kindest thing to do would be to drop you now, before you waste more time.
It's also possible that you weren't really applying your advisor's criticism - for example, you weren't taking him seriously when he told you not to get distracted by new ideas, but to focus on making progress on your original research. Your advisor felt that he was wasting his time because you weren't listening to his advice.
You should really talk to this professor's other students, and find out how they experience him as an advisor. If the other students get along just fine with him, and only you have this problem, then it's possible he just can't work with you.
However, in that case, he should really have spoken to you about the possibility of dropping you before he did it. (Not just making comments about your work, but explicitly telling you, "I can't keep working with you if this continues; this is what you need to do to show me you are making enough progress to continue.")
In any event, I'm going to answer this question as if you are a capable student, and your advisor is just unwilling to let you learn and work at a reasonable pace. (Obviously, I don't know you, so I don't know if this is true.)
In that case,
If your advisor isn't prepared to deal with a student who is capable, and clearly eager to learn and improve, then you should really reconsider wanting to work with him.
There is a professor like this in my department - brilliant, great to talk to, and there is a lot one can learn from him. But he is under a lot of pressure to produce results (he's new, like your advisor). He is constantly making "threats" to get his students to produce work (e.g., telling them their funding the next semester depends on whether their next conference paper is accepted - although he doesn't follow through on these threats). He isn't willing to let students grow and develop as researchers - he expects them to work up to his standards, immediately.
This professor's students are leaving him in droves. They are either leaving school with an M.S. (instead of sticking it out for the PhD), or switching to another advisor. As a result, he's only published one paper in the last two years (which is far, far below standard in his field).
So, you should think about whether you really want to work with this professor, and consider asking the grad coordinator for another advisor. If this advisor is not a capable advisor, you will not be successful with him, no matter how brilliant he is.
If you decide you really want to work with this professor, do not approach this meeting as a student who is begging an advisor to keep them on.
Rather, come as a student who is willing to stay with this advisor, but understands that both of you need to change for this to work. He will have to give you a reasonable chance to learn from, and apply, his constructive criticism. In return, you will agree to take his advice seriously, work hard, and do your best to improve and succeed.
Talk about how highly you value this professor's experience, and how much you want to learn from him. Explain that you take his concerns (about getting stuck with simple things and getting distracted with new ideas) seriously, and want to work on fixing those things - but that growth takes some time.
And of course, if you are able to work things out, and you continue with this advisor, make sure to talk to him often about what he expects from you, and how you are living up to his expectations. Work hard to apply his advice and improve your research skills, and make him aware of these efforts so that he doesn't think you are ignoring his advice.