diff --git a/hgext/rebase.py b/hgext/rebase.py
--- a/hgext/rebase.py
+++ b/hgext/rebase.py
@@ -1063,10 +1063,7 @@
     #   |\         None of A and B will be changed to D and rebase fails.
     #   A B   D
     if set(newps) == set(oldps) and dest not in newps:
-        # The error message is for compatibility. It's a bit misleading since
-        # rebase is not supposed to add new parents.
-        raise error.Abort(_('cannot use revision %d as base, '
-                            'result would have 3 parents') % rev)
+        raise error.Abort(_('cannot find new parents for revision %d') % rev)
 
     repo.ui.debug(" future parents are %d and %d\n" % tuple(newps))
 
diff --git a/tests/test-rebase-brute-force.t b/tests/test-rebase-brute-force.t
--- a/tests/test-rebase-brute-force.t
+++ b/tests/test-rebase-brute-force.t
@@ -23,7 +23,7 @@
      A: A':Z
      B: B':Z
     AB: A':Z B':Z
-     C: ABORT: cannot use revision 3 as base, result would have 3 parents
+     C: ABORT: cannot find new parents for revision 3
     AC: A':Z C':A'B
     BC: B':Z C':B'A
    ABC: A':Z B':Z C':A'B'
@@ -31,7 +31,7 @@
     AD: A':Z D':Z
     BD: B':Z D':B'
    ABD: A':Z B':Z D':B'
-    CD: ABORT: cannot use revision 3 as base, result would have 3 parents
+    CD: ABORT: cannot find new parents for revision 3
    ACD: A':Z C':A'B D':Z
    BCD: B':Z C':B'A D':B'
   ABCD: A':Z B':Z C':A'B' D':B'
@@ -49,7 +49,7 @@
     B: B':Z
     A: 
    BA: B':Z
-    C: ABORT: cannot use revision 3 as base, result would have 3 parents
+    C: ABORT: cannot find new parents for revision 3
    BC: B':Z C':B'A
    AC: 
   BAC: B':Z C':B'A
diff --git a/tests/test-rebase-obsolete.t b/tests/test-rebase-obsolete.t
--- a/tests/test-rebase-obsolete.t
+++ b/tests/test-rebase-obsolete.t
@@ -494,7 +494,7 @@
   not rebasing ignored 4:26805aba1e60 "C" (C)
   not rebasing ignored 5:4b61ff5c62e2 "E" (E)
   rebasing 6:f15c3adaf214 "F" (F tip)
-  abort: cannot use revision 6 as base, result would have 3 parents
+  abort: cannot find new parents for revision 6
   [255]
 
   $ cd ..
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
@@ -271,7 +271,7 @@
 
   $ hg rebase -s 6 -d 1
   rebasing 6:eea13746799a "G"
-  abort: cannot use revision 6 as base, result would have 3 parents
+  abort: cannot find new parents for revision 6
   [255]
   $ hg rebase --abort
   rebase aborted