diff -r 11212babc690 -r 39d1f83eb05d mercurial/discovery.py
--- a/mercurial/discovery.py	Fri Apr 27 13:18:09 2012 -0500
+++ b/mercurial/discovery.py	Tue Apr 24 16:32:44 2012 +0200
@@ -153,7 +153,10 @@
         branches = set(repo[n].branch() for n in outgoing.missing)
 
         # 2. Check for new branches on the remote.
-        remotemap = remote.branchmap()
+        if remote.local():
+            remotemap = phases.visiblebranchmap(remote)
+        else:
+            remotemap = remote.branchmap()
         newbranches = branches - set(remotemap)
         if newbranches and not newbranch: # new branch requires --new-branch
             branchnames = ', '.join(sorted(newbranches))