I am seeing the same error in my repository. We run bzr-index each night on each of our repositories. This error is occurring consistently for the last few nights in one out of 16 branches indexed. Local network access without proxy. Here is the message we are getting:

Indexing: /srv/bzr/groups/engineering/curl/rtsp

bzr: ERROR: exceptions.AssertionError: Somehow we ended up with too much compressed data, 4182 > 4096

Traceback (most recent call last):
  File "/usr/lib/python2.6/dist-packages/bzrlib/commands.py", line 842, in exception_to_return_code
    return the_callable(*args, **kwargs)
  File "/usr/lib/python2.6/dist-packages/bzrlib/commands.py", line 1037, in run_bzr
    ret = run(*run_argv)
  File "/usr/lib/python2.6/dist-packages/bzrlib/commands.py", line 654, in run_argv_aliases
    return self.run(**all_cmd_args)
  File "/usr/lib/python2.6/dist-packages/bzrlib/plugins/search/commands.py", line 41, in run
    _mod_index.index_url(trans.base)
  File "/usr/lib/python2.6/dist-packages/bzrlib/plugins/search/index.py", line 150, in index_url
    index.index_branch(branch, _last_revid)
  File "/usr/lib/python2.6/dist-packages/bzrlib/plugins/search/index.py", line 321, in index_branch
    self.index_revisions(branch, revs_to_index)
  File "/usr/lib/python2.6/dist-packages/bzrlib/plugins/search/index.py", line 336, in index_revisions
    outer_bar)
  File "/usr/lib/python2.6/dist-packages/bzrlib/plugins/search/index.py", line 384, in _index_revisions
    self._add_index(builder)
  File "/usr/lib/python2.6/dist-packages/bzrlib/plugins/search/index.py", line 397, in _add_index
    self._upload_transport)
  File "/usr/lib/python2.6/dist-packages/bzrlib/plugins/search/index.py", line 1107, in upload_index
    "terms", writer)
  File "/usr/lib/python2.6/dist-packages/bzrlib/plugins/search/index.py", line 994, in _add_index_to_pack
    index_file = index.finish()
  File "/usr/lib/python2.6/dist-packages/bzrlib/btree_index.py", line 425, in finish
    return self._write_nodes(self.iter_all_entries())[0]
  File "/usr/lib/python2.6/dist-packages/bzrlib/btree_index.py", line 378, in _write_nodes
    self._add_key(string_key, line, rows, allow_optimize=allow_optimize)
  File "/usr/lib/python2.6/dist-packages/bzrlib/btree_index.py", line 313, in _add_key
    rows[-1].finish_node()
  File "/usr/lib/python2.6/dist-packages/bzrlib/btree_index.py", line 67, in finish_node
    byte_lines, _, padding = self.writer.finish()
  File "/usr/lib/python2.6/dist-packages/bzrlib/chunk_writer.py", line 142, in finish
    % (self.bytes_out_len, self.chunk_size))
AssertionError: Somehow we ended up with too much compressed data, 4182 > 4096

bzr 2.0.2 on python 2.6.2 (Linux-2.6.28-16-server-i686-with-Ubuntu-9.04-jaunty)
arguments: ['/usr/bin/bzr', 'index', '/srv/bzr/groups/engineering/curl/rtsp']
encoding: 'ANSI_X3.4-1968', fsenc: 'ANSI_X3.4-1968', lang: None
plugins:
  bzrtools             /usr/lib/python2.6/dist-packages/bzrlib/plugins/bzrtools [2.0.0]
  extmerge             /usr/lib/python2.6/dist-packages/bzrlib/plugins/extmerge [unknown]
  gtk                  /usr/lib/python2.6/dist-packages/bzrlib/plugins/gtk [0.98.0dev1]
  launchpad            /usr/lib/python2.6/dist-packages/bzrlib/plugins/launchpad [2.0.2]
  netrc_credential_store /usr/lib/python2.6/dist-packages/bzrlib/plugins/netrc_credential_store [2.0.2]
  search               /usr/lib/python2.6/dist-packages/bzrlib/plugins/search [1.7.0dev]