KeyError when getting revision history

Branch.revision_history sometimes raises a KeyError.

>>> b = Branch.open('sftp://bazaar.launchpad.net/~leonardr/lazr.uri/cleanup2')
>>> b.revision_history()
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "<string>", line 4, in revision_history_read_locked
  File "/usr/lib/python2.6/dist-packages/bzrlib/branch.py", line 697, in revision_history
    history = self._gen_revision_history()
  File "/usr/lib/python2.6/dist-packages/bzrlib/branch.py", line 2438, in _gen_revision_history
    self._extend_partial_history(stop_index=last_revno-1)
  File "/usr/lib/python2.6/dist-packages/bzrlib/branch.py", line 2462, in _extend_partial_history
    for revision_id in iterator:
  File "/usr/lib/python2.6/dist-packages/bzrlib/repository.py", line 2160, in iter_reverse_revision_history
    parents = graph.get_parent_map([next_id])[next_id]
KeyError: '<email address hidden>'

Note that when cloning the same branch over sftp, you get the error:
    bzr: ERROR: Revision {<email address hidden>} not present in "lazr-20090108164351-t31f0dwb47eiieh9-4".

And over bzr+ssh, you get the error:
    bzr: ERROR: bzrlib.errors.ErrorFromSmartServer: Error received from smart server: ('error', "'AbsentContentFactory' object has no attribute 'get_bytes_as'")

along with a traceback.