You can rebuild the repository by doing a Mercurial to Mercurial conversion using hg convert
. Enable the convert extension first and create a branchmap to do the mapping of branch names from old to new:
a-bad-name new-name
another-bad-name better-name
You can use that to map multiple bad names into a single good name, for example.
After the conversion, you will have a new repository with the same history, but with different branch names. The changeset hashes will thus be different and people will have to reclone (but I think you're aware of this already).