If they want to change their U.S. birth certificate, even assuming that they can get a name change order in their nation of residence, they will have to do so under the laws of the undisclosed state.
That makes sense, but I was thinking more along the lines of changing a last name due to marriage, and that of course does not result in a birth certificate change.