Hm... that is odd.  It was a fresh checkout, which I then made some small changes to and tried to commit. 

"bzr ancestry" locally:
cyli@jinchuuriki-20080527230444-hbxas6yrzjng3vcn
cyli@jinchuuriki-20080527230729-9frniooeex8roncb
cyli@jinchuuriki-20080528040545-9e1ivprfkw3vy4ou
cyli@jinchuuriki-20080528043359-g0md7adzc1yfeo3x
cyli@legion-20080530200003-3kt65zc9yjaxej67
cyli@jinchuuriki-20080618141543-2hq42qg2ep9xy880
<email address hidden>

"bzr ancestry" on the server:
cyli@jinchuuriki-20080527230444-hbxas6yrzjng3vcn
cyli@jinchuuriki-20080527230729-9frniooeex8roncb
cyli@jinchuuriki-20080528040545-9e1ivprfkw3vy4ou
cyli@jinchuuriki-20080528043359-g0md7adzc1yfeo3x
cyli@legion-20080530200003-3kt65zc9yjaxej67

(I tried to commit first, and then tried to commit locally and do a push).

The results of "bzr upgrade":
bzr: ERROR: The branch format Bazaar-NG meta directory, format 1 is already at the most recent format.

The results of "bzr reconcile":
Reconciling branch file:///Users/cyli/Projects/wordnumbers/
revision_history ok.
Reconciling repository file:///Users/cyli/Projects/wordnumbers/
Reconciliation complete.

That seemed ok, but then I tried to run "bzr push" again and:
Using saved location: bzr+ssh://legion/home/cyli/Tonkatsu/Projects/wordnumbers/
This transport does not update the working tree of: bzr+ssh://legion/home/cyli/Tonkatsu/Projects/wordnumbers/. See 'bzr help working-trees' for more information.
Server is too old for fast get_parent_map, reconnecting.  (Upgrade the server to Bazaar 1.2 to avoid this)
bzr: ERROR: exceptions.AssertionError: 6 != 7

Traceback (most recent call last):
  File "/Library/Python/2.5/site-packages/bzrlib/commands.py", line 846, in run_bzr_catch_errors
    return run_bzr(argv)
  File "/Library/Python/2.5/site-packages/bzrlib/commands.py", line 797, in run_bzr
    ret = run(*run_argv)
  File "/Library/Python/2.5/site-packages/bzrlib/commands.py", line 499, in run_argv_aliases
    return self.run(**all_cmd_args)
  File "/Library/Python/2.5/site-packages/bzrlib/builtins.py", line 856, in run
    stop_revision=revision_id)
  File "/Library/Python/2.5/site-packages/bzrlib/decorators.py", line 127, in read_locked
    return unbound(self, *args, **kwargs)
  File "/Library/Python/2.5/site-packages/bzrlib/branch.py", line 1612, in push
    _override_hook_source_branch=_override_hook_source_branch)
  File "/Library/Python/2.5/site-packages/bzrlib/branch.py", line 1654, in _push_with_bound_branches
    result = self._basic_push(target, overwrite, stop_revision)
  File "/Library/Python/2.5/site-packages/bzrlib/branch.py", line 1673, in _basic_push
    target.update_revisions(self, stop_revision)
  File "/Library/Python/2.5/site-packages/bzrlib/remote.py", line 1537, in update_revisions
    other, stop_revision=stop_revision, overwrite=overwrite)
  File "/Library/Python/2.5/site-packages/bzrlib/decorators.py", line 165, in write_locked
    return unbound(self, *args, **kwargs)
  File "/Library/Python/2.5/site-packages/bzrlib/branch.py", line 1536, in update_revisions
    other_last_revision)
  File "/Library/Python/2.5/site-packages/bzrlib/decorators.py", line 165, in write_locked
    return unbound(self, *args, **kwargs)
  File "/Library/Python/2.5/site-packages/bzrlib/branch.py", line 1452, in set_last_revision_info
    raise AssertionError('%d != %d' % (len(history), revno))
AssertionError: 6 != 7

bzr 1.5 on python 2.5.1 (darwin)
arguments: ['/usr/local/bin/bzr', 'push']
encoding: 'UTF-8', fsenc: 'utf-8', lang: 'en_US.UTF-8'
plugins:
  bzrtools             /Library/Python/2.5/site-packages/bzrlib/plugins/bzrtools [1.5.0]
  launchpad            /Library/Python/2.5/site-packages/bzrlib/plugins/launchpad [unknown]
  qbzr                 /Library/Python/2.5/site-packages/bzrlib/plugins/qbzr [0.9.0]
  rebase               /Library/Python/2.5/site-packages/bzrlib/plugins/rebase [0.3.0dev0]
*** Bazaar has encountered an internal error.
    Please report a bug at https://bugs.launchpad.net/bzr/+filebug
    including this traceback, and a description of what you
    were doing when the error occurred.