diff --git a/hgext/histedit.py b/hgext/histedit.py
--- a/hgext/histedit.py
+++ b/hgext/histedit.py
@@ -928,7 +928,7 @@ def between(repo, old, new, keep):
             raise util.Abort(_('cannot edit history that contains merges'))
         root = ctxs[0] # list is already sorted by repo.set
         if not root.mutable():
-            raise util.Abort(_('cannot edit immutable changeset: %s') % root)
+            raise util.Abort(_('cannot edit public changeset: %s') % root)
     return [c.node() for c in ctxs]
 
 def makedesc(repo, action, rev):
diff --git a/hgext/mq.py b/hgext/mq.py
--- a/hgext/mq.py
+++ b/hgext/mq.py
@@ -1526,7 +1526,7 @@ class queue(object):
                                    "managed by this patch queue"))
             if not repo[self.applied[-1].node].mutable():
                 raise util.Abort(
-                    _("popping would remove an immutable revision"),
+                    _("popping would remove a public revision"),
                     hint=_('see "hg help phases" for details'))
 
             # we know there are no local changes, so we can make a simplified
@@ -1597,7 +1597,7 @@ class queue(object):
             if repo.changelog.heads(top) != [top]:
                 raise util.Abort(_("cannot refresh a revision with children"))
             if not repo[top].mutable():
-                raise util.Abort(_("cannot refresh immutable revision"),
+                raise util.Abort(_("cannot refresh public revision"),
                                  hint=_('see "hg help phases" for details'))
 
             cparents = repo.changelog.parents(top)
diff --git a/hgext/rebase.py b/hgext/rebase.py
--- a/hgext/rebase.py
+++ b/hgext/rebase.py
@@ -330,7 +330,7 @@ def rebase(ui, repo, **opts):
 
             root = min(rebaseset)
             if not keepf and not repo[root].mutable():
-                raise util.Abort(_("can't rebase immutable changeset %s")
+                raise util.Abort(_("can't rebase public changeset %s")
                                  % repo[root],
                                  hint=_('see "hg help phases" for details'))
 
@@ -869,7 +869,7 @@ def abort(repo, originalwd, target, stat
     immutable = [d for d in dstates if not repo[d].mutable()]
     cleanup = True
     if immutable:
-        repo.ui.warn(_("warning: can't clean up immutable changesets %s\n")
+        repo.ui.warn(_("warning: can't clean up public changesets %s\n")
                      % ', '.join(str(repo[r]) for r in immutable),
                      hint=_('see "hg help phases" for details'))
         cleanup = False
diff --git a/mercurial/obsolete.py b/mercurial/obsolete.py
--- a/mercurial/obsolete.py
+++ b/mercurial/obsolete.py
@@ -1214,7 +1214,7 @@ def createmarkers(repo, relations, flag=
                 localmetadata.update(rel[2])
 
             if not prec.mutable():
-                raise util.Abort("cannot obsolete immutable changeset: %s"
+                raise util.Abort("cannot obsolete public changeset: %s"
                                  % prec)
             nprec = prec.node()
             nsucs = tuple(s.node() for s in sucs)
diff --git a/tests/test-histedit-obsolete.t b/tests/test-histedit-obsolete.t
--- a/tests/test-histedit-obsolete.t
+++ b/tests/test-histedit-obsolete.t
@@ -219,7 +219,7 @@ Check that histedit respect immutability
   o  0:cb9a9f314b8b (public) a
   
   $ hg histedit -r '.~2'
-  abort: cannot edit immutable changeset: cb9a9f314b8b
+  abort: cannot edit public changeset: cb9a9f314b8b
   [255]
 
 
diff --git a/tests/test-mq-safety.t b/tests/test-mq-safety.t
--- a/tests/test-mq-safety.t
+++ b/tests/test-mq-safety.t
@@ -25,17 +25,17 @@ Try to operate on public mq changeset
   $ hg phase --public qbase
   $ echo babar >> foo
   $ hg qref
-  abort: cannot refresh immutable revision
+  abort: cannot refresh public revision
   (see "hg help phases" for details)
   [255]
   $ hg revert -a
   reverting foo
   $ hg qpop
-  abort: popping would remove an immutable revision
+  abort: popping would remove a public revision
   (see "hg help phases" for details)
   [255]
   $ hg qfold bar
-  abort: cannot refresh immutable revision
+  abort: cannot refresh public revision
   (see "hg help phases" for details)
   [255]
   $ hg revert -a
diff --git a/tests/test-rebase-interruptions.t b/tests/test-rebase-interruptions.t
--- a/tests/test-rebase-interruptions.t
+++ b/tests/test-rebase-interruptions.t
@@ -258,7 +258,7 @@ Change phase on B and B'
 Abort the rebasing:
 
   $ hg rebase --abort
-  warning: can't clean up immutable changesets 45396c49d53b
+  warning: can't clean up public changesets 45396c49d53b
   rebase aborted
 
   $ hg tglogp
diff --git a/tests/test-rebase-scenario-global.t b/tests/test-rebase-scenario-global.t
--- a/tests/test-rebase-scenario-global.t
+++ b/tests/test-rebase-scenario-global.t
@@ -308,7 +308,7 @@ Check rebasing public changeset
   nothing to rebase
   [1]
   $ hg rebase -d 5 -b 6
-  abort: can't rebase immutable changeset e1c4361dd923
+  abort: can't rebase public changeset e1c4361dd923
   (see "hg help phases" for details)
   [255]