Stanley,
It seems to me that the topmost menu should have the least index. So, calling Refresh seems to be a reasonable solution. Did you call Refresh after each click on a menu item? This should give the test engine time to rebuild the tree and re-assign indexes.
Another possible workaround is to address the needed items by their caption (text) rather than by indexes. You can try this and see if it works for you.
Anyhow, I'd say, the situation needs investigation. I'd suggest that you contact our Support Team and send them a problem description along with your Flex app demonstrating the problem. We will examine it and try to find a solution.