This took a while for me to discover, but if you have a TreeStore, that contains ModelData that IS TreeModels, since the TreeStore wraps the model data to a BasicTreeModel if you call add/remove on the TreeStore, it will only modify the wrapped BasicTreeModel relationships not the member data (which may be a treeModel). I guess I am not sure of a situation whereby you would have a non-wrapped TreeModel representing data for another tree and so perhaps the code should be modified to update the relationships in the unwraped model data of TreeModel type. As it is, I had to extend the TreeStore to override a few methods to keep this in sync.
I should explain my situation, since it might be a little obtuse. I have three stores that represent objects in my system. Collections, Albums and Countries. These are used be a variety of controllers/widgets and represent the physical model. My tree store is made up on Collections that have Albums that have Countries. I have a ReferenceTreeModel which simply has a name, a type and a pointer (ID) to the model in one of the three "real" stores. If I need the physical model data represented by the tree node, I can obtain this quickly (it also means I don't need to worry about maintainng two stores of "Countries" for example). In some respects, I suppose I do not really need ReferenceTreeModel to extend TreeModel (ie. it is simply a pointer extending BaseModel).