diff -r 098cb7bd46a7 -r 3324345a498e mercurial/destutil.py
--- a/mercurial/destutil.py	Mon Feb 15 14:35:26 2016 +0000
+++ b/mercurial/destutil.py	Tue Feb 09 23:35:21 2016 +0000
@@ -235,7 +235,8 @@
             branch = ctx.branch()
 
     bheads = repo.branchheads(branch)
-    if onheadcheck and not repo.revs('%ld and %ln', sourceset, bheads):
+    onhead = repo.revs('%ld and %ln', sourceset, bheads)
+    if onheadcheck and not onhead:
         # Case A: working copy if not on a head. (merge only)
         #
         # This is probably a user mistake We bailout pointing at 'hg update'
@@ -267,6 +268,10 @@
         elif len(repo.heads()) > 1:
             msg, hint = msgdestmerge['nootherbranchheads'][action]
             msg %= branch
+        elif not onhead:
+            # if 'onheadcheck == False' (rebase case),
+            # this was not caught in Case A.
+            msg, hint = msgdestmerge['nootherheadsbehind'][action]
         else:
             msg, hint = msgdestmerge['nootherheads'][action]
         raise error.NoMergeDestAbort(msg, hint=hint)