There are two possibilities here Frank.
If you are creating an instance of your state machine, you should get one of the anonymous objects I mentioned earlier. By UML convention this is given a blank name, and displayed as :<classifierName>. You can open the properties dialog for this instance and give it a name, which will then appear as <instanceName>:<classifierName>. This is not an EA-specific policy; this is how UML works.
In this case the part of the name after the colon refers to the classifier, not the instance. Each instance is an (independent) occurrence of the classifier. It may be given a name, or it may be anonymous, but it is still of the same type as the classifier. [Sort of like renaming a pet cat. It will still be a cat.]
Second, if you are creating a "simple link" (to use the EA vernacular) to the object, you are actually referring to the same definition as the one you already have. To be specific, you have not copied the original state machine; the same machine is merely shown on both diagrams. To confirm this check the Project Browser, and you will observe that the state machine only appears once. If you delete it (using only the delete key) from either diagram it will still be present in the Project Browser, and the other diagram. If you rename it in either diagram, it will be renamed in all three places. If you delete it from the Project Browser - please don't actually do this on your working copy; just trust me - it will be gone from the entire EA project.
That's why the non-instance machine seems to always have the same name. There's only one machine, and it has the same name no matter where you reference it.
HTH, David