diff -r e6de4761d26f -r eaa5fcc5bd20 mercurial/discovery.py
--- a/mercurial/discovery.py	Fri Aug 24 16:52:45 2012 +0200
+++ b/mercurial/discovery.py	Sun Aug 26 00:25:33 2012 +0200
@@ -264,6 +264,8 @@
     error = None
     unsynced = False
     allmissing = set(outgoing.missing)
+    allfuturecommon = set(c.node() for c in repo.set('%ld', outgoing.common))
+    allfuturecommon.update(allmissing)
     for branch, heads in headssum.iteritems():
         if heads[0] is None:
             # Maybe we should abort if we push more that one head
@@ -293,11 +295,11 @@
             # more tricky for unsynced changes.
             newhs = set()
             for nh in candidate_newhs:
-                if repo[nh].phase() <= phases.public:
+                if nh in repo and repo[nh].phase() <= phases.public:
                     newhs.add(nh)
                 else:
                     for suc in obsolete.anysuccessors(repo.obsstore, nh):
-                        if suc != nh and suc in allmissing:
+                        if suc != nh and suc in allfuturecommon:
                             break
                     else:
                         newhs.add(nh)