depending on time scales and budget you could try a combination of both.
start by inviting trusted, regular users to try out your new design and give feedback
then act of this feedback to improve your new designs
next start migrating a subset of your users onto the new design, giving them plenty of notice and the option to switch back
again analyse usage and ask direct questions
finally you can set a date for complete switch over and notify users, giving them the option to try the new designs now, or pushing everyone over to the new design with the option to switch back
eventually your goal would be to switch everyone over and remove the old designs, but to have a product that so well tested in the real world that even reluctant users will not get lost should adapt without too much friction
you will notice sites like facebook and google have done this when they overhaul their UIs, a good example is the switch to the timeline in facebook, or indeed the recent 'invite only' access to the new google maps.