--- a/mercurial/commands.py	Mon Apr 08 17:57:42 2013 -0500
+++ b/mercurial/commands.py	Tue Apr 09 09:40:40 2013 -0700
@@ -2078,8 +2078,12 @@
 
     labels = set()
     labels.update(t[0] for t in repo.tagslist())
-    labels.update(repo[n].branch() for n in repo.heads())
     labels.update(repo._bookmarks.keys())
+    for heads in repo.branchmap().itervalues():
+        for h in heads:
+            ctx = repo[h]
+            if not ctx.closesbranch():
+                labels.add(ctx.branch())
     completions = set()
     if not args:
         args = ['']

--- a/tests/test-completion.t	Mon Apr 08 17:57:42 2013 -0500
+++ b/tests/test-completion.t	Tue Apr 09 09:40:40 2013 -0700
@@ -329,8 +329,10 @@
   Fum
   default
   fee
+  fie
   fo
   tip
   $ hg debuglabelcomplete f
   fee
+  fie
   fo