Yes, you would need to publish a new version of the package with a different name. But the history of what happened (and consequently anyone depending on the old name) would be preserved.