I think a name like My::Module::Beta is a really bad idea. It pollutes the namespace with junk. Better ideas:

1. If it's such a radical redesign of the interface, consider using a different name altogether that better reflects what the module does;
2. Increase the version number, and note that it's beta by putting an underscore in the version (ie, 2.00_01). Also note very prominently in the README and POD that the interface is redesigned
3. Use different function or method names, and have the old function names call the new functions. In your docs note that the old interface is deprecated, and in a far future version remove them