When you want to rename a test in Visual Studio you need to open that test and all of its child tests in the Test Studio's Test Explorer, otherwise the changes will not be reflected and next time you run the renamed test it will not be able to find its child tests. 

Here's a video demonstrating the issue:
http://screencast.com/t/xPIXORUMx