I've just pushed out version 0.16.2 of my Python B-tree library. This should fix all remaining problems of B-tree nodes being modified in place while in the upload queue. This is done by never modifying nodes after they have been put into the node store. Performance suffers, but it's worth it for correctness.
If anyone would like take a stab at making it faster again, there's instructions in the README file for getting started with hacking the code, or you can ask me. Profiling indicates that it might be quite helpful to keep the root node of a tree out of the store until the forest-of-trees gets committed.
On the other hand, the performance of obnam has not been greatly affected by these changes, since it spends most of its time reading and writing the contents of files being backed up.