--- a/mercurial/discovery.py	Tue Jun 26 15:08:10 2012 -0500
+++ b/mercurial/discovery.py	Tue Jun 26 23:05:25 2012 +0200
@@ -225,7 +225,6 @@
     # If there are more heads after the push than before, a suitable
     # error message, depending on unsynced status, is displayed.
     error = None
-    remotebookmarks = remote.listkeys('bookmarks')
     localbookmarks = repo._bookmarks
 
     for branch in branches:
@@ -234,9 +233,14 @@
         dhs = None
         if len(newhs) > len(oldhs):
             # strip updates to existing remote heads from the new heads list
-            bookmarkedheads = set([repo[bm].node() for bm in localbookmarks
-                                   if bm in remotebookmarks and
-                                   remote[bm] == repo[bm].ancestor(remote[bm])])
+            remotebookmarks = remote.listkeys('bookmarks')
+            bookmarkedheads = set()
+            for bm in localbookmarks:
+                rnode = remotebookmarks.get(bm)
+                if rnode and rnode in repo:
+                    lctx, rctx = repo[bm], repo[rnode]
+                    if rctx == lctx.ancestor(rctx):
+                        bookmarkedheads.add(lctx.node())
             dhs = list(newhs - bookmarkedheads - oldhs)
         if dhs:
             if error is None:

--- a/tests/test-bookmarks-pushpull.t	Tue Jun 26 15:08:10 2012 -0500
+++ b/tests/test-bookmarks-pushpull.t	Tue Jun 26 23:05:25 2012 +0200
@@ -177,8 +177,18 @@
   adding f2
   created new head
   $ hg book -f Y
-  $ hg push ../a
-  pushing to ../a
+
+  $ cat <<EOF > ../a/.hg/hgrc
+  > [web]
+  > push_ssl = false
+  > allow_push = *
+  > EOF
+
+  $ hg -R ../a serve -p $HGPORT2 -d --pid-file=../hg2.pid
+  $ cat ../hg2.pid >> $DAEMON_PIDS
+
+  $ hg push http://localhost:$HGPORT2/
+  pushing to http://localhost:$HGPORT2/
   searching for changes
   abort: push creates new remote head 4efff6d98829!
   (did you forget to merge? use push -f to force)