diff --git a/mercurial/localrepo.py b/mercurial/localrepo.py
--- a/mercurial/localrepo.py
+++ b/mercurial/localrepo.py
@@ -1503,13 +1503,14 @@ class localrepository(repo.repository):
         update, updated_heads = self.findoutgoing(remote, common, remote_heads)
         msng_cl, bases, heads = self.changelog.nodesbetween(update, revs)
 
-        def checkbranch(lheads, rheads, branchname=None):
+        def checkbranch(lheads, rheads, lheadcnt, branchname=None):
             '''
             check whether there are more local heads than remote heads on
             a specific branch.
 
             lheads: local branch heads
             rheads: remote branch heads
+            lheadcnt: total number of local branch heads
             '''
 
             warn = 0
@@ -1544,7 +1545,7 @@ class localrepository(repo.repository):
                 else:
                     msg = _("abort: push creates new remote heads!\n")
                 self.ui.warn(msg)
-                if len(lheads) > len(rheads):
+                if lheadcnt > len(rheads):
                     self.ui.status(_("(did you forget to merge?"
                                      " use push -f to force)\n"))
                 else:
@@ -1570,12 +1571,16 @@ class localrepository(repo.repository):
                 if remote.capable('branchmap'):
                     remotebrheads = remote.branchmap()
 
+                    lbrmap = self.branchmap()
+                    localbrheads = {}
                     if not revs:
-                        localbrheads = self.branchmap()
+                        for br, hds in lbrmap.iteritems():
+                            localbrheads[br] = (len(hds), hds)
                     else:
-                        localbrheads = {}
                         ctxgen = (self[n] for n in msng_cl)
                         self._updatebranchcache(localbrheads, ctxgen)
+                        for br, hds in localbrheads.iteritems():
+                            localbrheads[br] = (len(lbrmap[br]), hds)
 
                     newbranches = list(set(localbrheads) - set(remotebrheads))
                     if newbranches: # new branch requires --force
@@ -1586,13 +1591,14 @@ class localrepository(repo.repository):
                         # propose 'push -b .' in the msg too?
                         self.ui.status(_("(use 'hg push -f' to force)\n"))
                         return None, 0
-                    for branch, lheads in localbrheads.iteritems():
+                    for branch, x in localbrheads.iteritems():
                         if branch in remotebrheads:
+                            headcnt, lheads = x
                             rheads = remotebrheads[branch]
-                            if not checkbranch(lheads, rheads, branch):
+                            if not checkbranch(lheads, rheads, headcnt, branch):
                                 return None, 0
                 else:
-                    if not checkbranch(heads, remote_heads):
+                    if not checkbranch(heads, remote_heads, len(heads)):
                         return None, 0
 
             if inc:
diff --git a/tests/test-push-warn b/tests/test-push-warn
--- a/tests/test-push-warn
+++ b/tests/test-push-warn
@@ -56,15 +56,15 @@ hg push -r 3 ../c; echo $?
 hg push -r 3 -r 4 ../c; echo $?
 hg push -f -r 3 -r 4 ../c; echo $?
 hg push -r 5 ../c; echo $?
+hg in ../c
 
-# issue 450
+echo % issue 450
 hg init ../e
 hg push -r 0 ../e ; echo $?
 hg push -r 1 ../e ; echo $?
 
 cd ..
 
-# issue 736
 echo % issue 736
 hg init f
 cd f
diff --git a/tests/test-push-warn.out b/tests/test-push-warn.out
--- a/tests/test-push-warn.out
+++ b/tests/test-push-warn.out
@@ -45,7 +45,7 @@ 0
 pushing to ../c
 searching for changes
 abort: push creates new remote heads on branch 'default'!
-(you should pull and merge or use push -f to force)
+(did you forget to merge? use push -f to force)
 1
 pushing to ../c
 searching for changes
@@ -66,6 +66,10 @@ adding manifests
 adding file changes
 added 1 changesets with 1 changes to 1 files (-1 heads)
 0
+comparing with ../c
+searching for changes
+no changes found
+% issue 450
 pushing to ../e
 searching for changes
 adding changesets
@@ -107,7 +111,7 @@ 1
 pushing to ../f
 searching for changes
 abort: push creates new remote heads on branch 'a'!
-(you should pull and merge or use push -f to force)
+(did you forget to merge? use push -f to force)
 1
 % push replacement head on existing branches
 pushing to ../f