diff -r 1f94ef2bd88d -r f1460af18c50 mercurial/branchmap.py
--- a/mercurial/branchmap.py	Mon Feb 29 09:26:43 2016 -0800
+++ b/mercurial/branchmap.py	Mon Mar 07 17:26:47 2016 -0800
@@ -55,6 +55,7 @@
         if not partial.validfor(repo):
             # invalidate the cache
             raise ValueError('tip differs')
+        cl = repo.changelog
         for l in lines:
             if not l:
                 continue
@@ -62,9 +63,9 @@
             if state not in 'oc':
                 raise ValueError('invalid branch state')
             label = encoding.tolocal(label.strip())
-            if not node in repo:
-                raise ValueError('node %s does not exist' % node)
             node = bin(node)
+            if not cl.hasnode(node):
+                raise ValueError('node %s does not exist' % hex(node))
             partial.setdefault(label, []).append(node)
             if state == 'c':
                 partial._closednodes.add(node)