I'm not (even near) expert on this matter. And I'm also curious about a solution.

How about making new version of that old module, specifying that it's name changed to xxx and that anyone who wants to use it, should use the new one from now on. Put that as first thing in the docs.

And change code to something like

package Old::Module;
use base 'New::Module';
1;
[download]

Would that do the trick? Actually when I think about it. If module is written with inheritance in mind (and since you're rewriting it anyway, you can add it if needed) that should work perfectly. And people could even continue to 'use Old::Module;'.

But then again, what's the point? Probably the new name is/will describe better what module does, and where it belongs (folder/namespace)...