diff -r 9510b0e9480b -r 5c153c69fdb2 mercurial/bookmarks.py
--- a/mercurial/bookmarks.py	Fri Aug 29 12:17:53 2014 +0200
+++ b/mercurial/bookmarks.py	Tue Aug 26 04:58:41 2014 -0700
@@ -228,7 +228,8 @@
     w = repo.wlock()
     try:
         marks = repo._bookmarks
-        if hex(marks.get(key, '')) != old:
+        existing = hex(marks.get(key, ''))
+        if existing != old and existing != new:
             return False
         if new == '':
             del marks[key]