diff --git a/mercurial/bookmarks.py b/mercurial/bookmarks.py
--- a/mercurial/bookmarks.py
+++ b/mercurial/bookmarks.py
@@ -209,7 +209,7 @@ def updatefromremote(ui, repo, remote, p
                 cl = repo[nl]
                 if cl.rev() >= cr.rev():
                     continue
-                if cr in cl.descendants():
+                if validdest(repo, cl, cr):
                     repo._bookmarks[k] = cr.node()
                     changed = True
                     ui.status(_("updating bookmark %s\n") % k)
@@ -252,3 +252,7 @@ def diff(ui, repo, remote):
         ui.status(_("no changed bookmarks found\n"))
         return 1
     return 0
+
+def validdest(repo, old, new):
+    """Is the new bookmark destination a valid update from the old one"""
+    return new in old.descendants()
diff --git a/mercurial/discovery.py b/mercurial/discovery.py
--- a/mercurial/discovery.py
+++ b/mercurial/discovery.py
@@ -7,7 +7,7 @@
 
 from node import nullid, short
 from i18n import _
-import util, setdiscovery, treediscovery, phases, obsolete
+import util, setdiscovery, treediscovery, phases, obsolete, bookmarks
 
 def findcommonincoming(repo, remote, heads=None, force=False):
     """Return a tuple (common, anyincoming, heads) used to identify the common
@@ -255,7 +255,7 @@ def checkheads(repo, remote, outgoing, r
         rnode = remotebookmarks.get(bm)
         if rnode and rnode in repo:
             lctx, rctx = repo[bm], repo[rnode]
-            if rctx == lctx.ancestor(rctx):
+            if bookmarks.validdest(repo, rctx, lctx):
                 bookmarkedheads.add(lctx.node())
 
     # 3. Check for new heads.
diff --git a/mercurial/localrepo.py b/mercurial/localrepo.py
--- a/mercurial/localrepo.py
+++ b/mercurial/localrepo.py
@@ -1992,7 +1992,7 @@ class localrepository(object):
                 if nr in self:
                     cr = self[nr]
                     cl = self[nl]
-                    if cl in cr.descendants():
+                    if bookmarks.validdest(self, cr, cl):
                         r = remote.pushkey('bookmarks', k, nr, nl)
                         if r:
                             self.ui.status(_("updating bookmark %s\n") % k)