diff -r 5a4f220fbfca -r c6e033a7dd38 mercurial/bookmarks.py
--- a/mercurial/bookmarks.py	Wed Dec 12 02:38:14 2012 +0100
+++ b/mercurial/bookmarks.py	Tue Jan 15 02:59:12 2013 +0100
@@ -198,7 +198,7 @@
     rb = remote.listkeys('bookmarks')
     changed = False
     localmarks = repo._bookmarks
-    for k in rb.keys():
+    for k in sorted(rb):
         if k in localmarks:
             nr, nl = rb[k], localmarks[k]
             if nr in repo: