Recently I have been contemplating changing the namespace for one of my modules

Why?

How is it best to handle a namespace change?

By not changing the namespace (picking a good one to begin with) :)

Should I release an updated module version whose sole purpose is to install the renamed module in the new namespace on CPAN?

Technically, that's the only way to "rename" a module, by releasing a new module with a different name. But if thats all you're going to do, you really shouldn't. But, if you insist on doing it, make sure you release a final version under the old name, making it clear to its users that the name has changed, and what kind of support they can expect...