diff -r 6e9b9f6c117c -r c7dbd6c4877a mercurial/localrepo.py
--- a/mercurial/localrepo.py	Mon Apr 26 04:01:13 2010 +0200
+++ b/mercurial/localrepo.py	Mon Apr 26 15:58:36 2010 -0400
@@ -315,6 +315,8 @@
             self.nodetagscache = {}
             for t, n in self.tags().iteritems():
                 self.nodetagscache.setdefault(n, []).append(t)
+            for tags in self.nodetagscache.itervalues():
+                tags.sort()
         return self.nodetagscache.get(node, [])
 
     def _branchtags(self, partial, lrev):