Mostly summarising what other people have already said, but:

• Yes, do it. It sounds like an improvement.

• Document the changes clearly.

• Bump the major version number.

• Release a trial version (either an underscore in the version number or "-TRIAL" in the tarball name) at least a month before releasing it as stable.

• If there are other CPAN modules that depend on your module (especially if they're popular), do the authors a favour and download those modules and test them against your trial version. Submit bug reports and maybe patches if you've broken them.