diff -r d044a762f47f -r daf32ebfde6b mercurial/bookmarks.py
--- a/mercurial/bookmarks.py	Thu Oct 25 23:36:03 2012 +0200
+++ b/mercurial/bookmarks.py	Thu Oct 25 23:43:52 2012 +0200
@@ -256,7 +256,7 @@
     elif repo.obsstore:
         # We only need this complicated logic if there is obsolescence
         # XXX will probably deserve an optimised revset.
-
+        nm = repo.changelog.nodemap
         validdests = set([old])
         plen = -1
         # compute the whole set of successors or descendants
@@ -268,7 +268,8 @@
                     # obsolescence marker does not apply to public changeset
                     succs.update(obsolete.allsuccessors(repo.obsstore,
                                                         [c.node()]))
-            validdests = set(repo.set('%ln::', succs))
+            known = (n for n in succs if nm.get(n) is not None)
+            validdests = set(repo.set('%ln::', known))
         validdests.remove(old)
         return new in validdests
     else: