"Deprecate the old module and release"

Agreed, but as I've learned through experience, one can't dump a "shit... I made a mistake", I'll rename this when even one user is using your distribution. It sucks, and it's a learning curve... my advice is ask here on Perlmonks (or any other site that is legit for CPAN naming) then do due diligence. It's a hairy situation, because there's no one confirmation that can be made.

If you've already published a distribution, don't dump it if you even smell a single person is using it. Burn another namespace, but ask first. Again modules <at> cpan.org.