I've done exactly this a number of times. The approach I generally take is to define a completely new ADT, mark the old one as deprecated, and then simply plough through the compiler warnings and errors, which is a mostly mechanical process.
On occasion I've written a (temporary) injection from the old datatype into the new one which lets you make the changes piecemeal (by topologically sorting the usages) which is nice as if there's any risk of making a mistake then tools like `git bisect` can help you find the slip in the sea of otherwise identical changes. Doesn't always work smoothly but it's often ok.
This also has the advantage that you don't have to fix all the usages in third-party code or dependent libraries straight away. The deprecation step need not be immediate, depending on how stable your API is supposed to be.
Cheers,
David