A compatibility layer (either in the same package or in a new namespace) can soon become very ugly, for example when you introduce new data structures. When such an compatibility layer would be absolutely necessary, my vote is: don't do the API changes unless the refactoring is not much more than method renamings.

Another option is a long transition phase with developer releases on CPAN. When you are happy with the new API, increment the major version number and release.