Just tried to reproduced using a simple button that does the following:
protected void Button1_Click(object sender, EventArgs e)
{
flyTreeView.Nodes[0].ChildNodes[1].Remove();
}
Without success.
Looks the issue is related to server-side templates? Do you use server-side templates for nodes?
Can you create a simple test page with single FlyTreeView control in it that reproduces the issue?