Broken as well in here, using kfish's git-bzr (http://github.com/kfish/git-bzr) HEAD, bazaar 2.1 and fastimport 0.9.0 dev

$ git bzr push $remote
11:04:16 Starting import ...
Could not import marks file .git/bzr-git/$remote-bzr-map - not importing marks
ABORT: exception occurred processing commit :3410
bzr: ERROR: exceptions.KeyError: ':3408'

Traceback (most recent call last):
  File "/opt/local/Library/Frameworks/Python.framework/Versions/2.6/lib/python2.6/site-packages/bzrlib/commands.py", line 853, in exception_to_return_code
    return the_callable(*args, **kwargs)
  File "/opt/local/Library/Frameworks/Python.framework/Versions/2.6/lib/python2.6/site-packages/bzrlib/commands.py", line 1055, in run_bzr
    ret = run(*run_argv)
  File "/opt/local/Library/Frameworks/Python.framework/Versions/2.6/lib/python2.6/site-packages/bzrlib/commands.py", line 661, in run_argv_aliases
    return self.run_direct(**all_cmd_args)
  File "/opt/local/Library/Frameworks/Python.framework/Versions/2.6/lib/python2.6/site-packages/bzrlib/commands.py", line 665, in run_direct
    return self._operation.run_simple(*args, **kwargs)
  File "/opt/local/Library/Frameworks/Python.framework/Versions/2.6/lib/python2.6/site-packages/bzrlib/cleanup.py", line 122, in run_simple
    self.cleanups, self.func, *args, **kwargs)
  File "/opt/local/Library/Frameworks/Python.framework/Versions/2.6/lib/python2.6/site-packages/bzrlib/cleanup.py", line 156, in _do_with_cleanups
    result = func(*args, **kwargs)
  File "/opt/local/Library/Frameworks/Python.framework/Versions/2.6/lib/python2.6/site-packages/bzrlib/plugins/fastimport/__init__.py", line 384, in run
    params, verbose, user_map=user_map)
  File "/opt/local/Library/Frameworks/Python.framework/Versions/2.6/lib/python2.6/site-packages/bzrlib/plugins/fastimport/__init__.py", line 111, in _run
    return proc.process(p.iter_commands)
  File "/opt/local/Library/Frameworks/Python.framework/Versions/2.6/lib/python2.6/site-packages/bzrlib/plugins/fastimport/processor.py", line 95, in process
    self._process(command_iter)
  File "/opt/local/Library/Frameworks/Python.framework/Versions/2.6/lib/python2.6/site-packages/bzrlib/plugins/fastimport/processors/generic_processor.py", line 283, in _process
    processor.ImportProcessor._process(self, command_iter)
  File "/opt/local/Library/Frameworks/Python.framework/Versions/2.6/lib/python2.6/site-packages/bzrlib/plugins/fastimport/processor.py", line 117, in _process
    handler(self, cmd)
  File "/opt/local/Library/Frameworks/Python.framework/Versions/2.6/lib/python2.6/site-packages/bzrlib/plugins/fastimport/processors/generic_processor.py", line 493, in commit_handler
    handler.process()
  File "/opt/local/Library/Frameworks/Python.framework/Versions/2.6/lib/python2.6/site-packages/bzrlib/plugins/fastimport/processor.py", line 200, in process
    self.pre_process_files()
  File "/opt/local/Library/Frameworks/Python.framework/Versions/2.6/lib/python2.6/site-packages/bzrlib/plugins/fastimport/bzr_commit_handler.py", line 582, in pre_process_files
    super(InventoryDeltaCommitHandler, self).pre_process_files()
  File "/opt/local/Library/Frameworks/Python.framework/Versions/2.6/lib/python2.6/site-packages/bzrlib/plugins/fastimport/bzr_commit_handler.py", line 84, in pre_process_files
    for p in parents]
KeyError: ':3408'

bzr 2.1.0 on python 2.6.4 (Darwin-10.2.0-i386-64bit)
arguments: ['/opt/local/bin/bzr', 'fast-import', '--import-marks=.git/bzr-git/$remote-bzr-map', '--export-marks=.git/bzr-git/$remote-bzr-map', '-']
encoding: 'UTF-8', fsenc: 'utf-8', lang: 'en_GB.UTF-8'
plugins:
  bzrtools             /opt/local/Library/Frameworks/Python.framework/Versions/2.6/lib/python2.6/site-packages/bzrlib/plugins/bzrtools [2.1.0]
  extmerge             /opt/local/Library/Frameworks/Python.framework/Versions/2.6/lib/python2.6/site-packages/bzrlib/plugins/extmerge [unknown]
  fastimport           /opt/local/Library/Frameworks/Python.framework/Versions/2.6/lib/python2.6/site-packages/bzrlib/plugins/fastimport [0.9.0dev]
  launchpad            /opt/local/Library/Frameworks/Python.framework/Versions/2.6/lib/python2.6/site-packages/bzrlib/plugins/launchpad [2.1.0]
  netrc_credential_store /opt/local/Library/Frameworks/Python.framework/Versions/2.6/lib/python2.6/site-packages/bzrlib/plugins/netrc_credential_store [2.1.0]
  news_merge           /opt/local/Library/Frameworks/Python.framework/Versions/2.6/lib/python2.6/site-packages/bzrlib/plugins/news_merge [2.1.0]
  qbzr                 /opt/local/Library/Frameworks/Python.framework/Versions/2.6/lib/python2.6/site-packages/bzrlib/plugins/qbzr [0.17.0]
  rebase               /opt/local/Library/Frameworks/Python.framework/Versions/2.6/lib/python2.6/site-packages/bzrlib/plugins/rebase [0.5.5]

*** Bazaar has encountered an internal error.  This probably indicates a
    bug in Bazaar.  You can help us fix it by filing a bug report at
        https://bugs.launchpad.net/bzr/+filebug
    including this traceback and a description of the problem.