I'm surprised that RemoveAt works at all for you with the treeInstances array, since it's a built-in array and doesnt' (as far as I know) support the RemoveAt function.

When I have modified or set the treeInstances array in the past, I've always built or modified them in a variable sized array (such as an ArrayList or List), and then dumped the entire new array back into terrainData.treeInstances as a whole, like this:

// get a copy of the trees, into a new dynamic collection
List<TreeInstance> newTrees = new List<TreeInstance>(terrainData.treeInstances);

// modify the collection
newTrees.RemoveAt(n);

// replace the trees back into the terrainData as a built-in array
terrainData.treeInstances = newTrees.ToArray();

And also, make sure you are calling:

terrainData.RecalculateTreePositions();

after modifying the tree instances array.

Note
Some of these functions are undocumented. Any future updates of the unity engine might change or remove these functions from the API. This means your project may not work in future versions of the Unity editor, and webplayer builds may not work with future versions of the plugin.

Here is how:

        // Now refresh the terrain, getting rid of the darn collider
        float[,] heights = terrain.GetHeights(0, 0, 0, 0);
        terrain.SetHeights(0, 0, heights);

You also may need to disable and reenable the terrain collider.

Here is a thread that gives more details: http://forum.unity3d.com/threads/110354-Finally-Removing-trees-AND-the-colliders

Sounds kind of like a bug. Try submitting a bug report.