I know, I know, this thread is as old as walking backwards, but hey, I came here looking for a solution and although Orbital Shark's answer not quite solved what I was expecting, I went looking by myself and found a way to get rid of the old, outdated network connections.
The issue was, I could not rename my Wireless connection. But that's because I had already renamed an old Wireless connection before. Thus, Windows did not allowed me to rename this new one because it already knew about another one with this very same name. So I went in the Windows registry and searched for my network connection. When I found it, I just deleted the key and its subkeys and voilá, problem has been solved.
Please note, this is a very unsafe method, particularly if you are not sure on what to do or if you have no much expertise playing with Windows Registry. So let me do a quick tutorial with an image to better explain:
0. Create a system restore point before messing up things;
1. Open an command prompt with administrative privileges;
2. Type "regedit" without quotes to open Registry Editor application;
3. Click on Edit, then Find... (or press Ctrl+F);
4. Type the network name you are looking for - in my case, "Wireless Network Connection" (again, no quotes);
5. When you find a key, it will look like the following:
6. To find out if this belongs the current network interface or to an older interface, take a look at "PnpInstanceID" value (in my picture it is shown right below "Name" key). Any valid network adapter will have an Instance ID value similar to "PCI\VEN_1234&DEV_5678&SUBSYS_12345678&REV_01\blablabla". That is because the hardware is currently detected by the OS, so it is pointing to the hardware.
7. Assuming you found a key not pointing to any currently active interface, you can select the parent key and delete it. In the above image, the parent key is the "{BD8D2B3D-3E6A-40EA-9C59-F5CF756220BA}" key, as found on the left panel.
8. You may need to search a couple more times to find out all old entries. They may be multiple. Proceed as above for removal of any other inactive interfaces;
9. Now you can proceed as Orbital Shark posted above, and Windows will accept the "previous" name in this "new" connection.
Again, I apologise by ressing such old thread. I hope this may be helpful to anyone as it was to me.