Making your new mouse work for you
I found for a long while after getting a new mouse I used to have this issue. However unfortunately, though it does improve with practice I found generally it is more necessary to reconfigure the new mouse.
Specifically, though many mice offer very high DPI, this does not actually help your game-play at all unless your style revolves around fast twitch like movements with minimal accuracy.
My first suggestion if you have not done so already would be to disable mouse acceleration, mouse acceleration makes the movement much less predictable to your brain and therefore makes your "muscle memory", which is all about your brain predicting and recalling what a movement of your arm will do to the game, much less accurate. This article explains some of the issues with the unpredictability of mouse acceleration.
Next, if this does not help, you will need to try and fine tune the dpi of your mouse, doing this is difficult, but the only sure technique is to adjust it up or down incrementally and then try it out of a little while until you get a feel that it is moving "right" when compared to what you feel it should be doing, it is difficult to explain but if you experiment with this you will understand when you find it.
The application that comes with the mouse driver usually has the ability to adjust the DPI, however if not there are a number of free downloadable tools that can do so for common mice, I shall leave it an exercise to the reader to find the right tool for your model.
Finally, as I said at the start, a new mouse does take some training to regain former performance, however if you have configured it correctly, this adjustment will be based around the shape, grip style and weight, not a problematic sensitivity.
Changing your play style for a new DPI
Note, it is valid to change sensitivity if you do wish to change your play style, however it is a poor plan to combine this with a new mouse and getting used to that, if you wish to try this wait until you are used to your new mouse, then adjust the DPI fractionally up or down as required, doing this by only a little each time until you are used to the new setting, then if you need to do so further do it again.
Do not try and make a big jump or change many things at once as you will be practically thrown back to square one and practice will not help much as you will not be adjusting your style but building a completely new one.