Denver is right that embeds get processed at the end of template parsing by default, therefore the value of the "name" variable will always have the last value. What you could do is use the parameter process="start" so that the embed code is included before template parsing starts.
{exp:stash:set name="name"}John{/exp:stash:set}
{stash:embed name="message" process="start"}
{exp:stash:set name="name"}Jane{/exp:stash:set}
{stash:embed name="message" process="start" random}
Note that you would need to access your "name" variable as a tag in the embed, and that this tag should not be nested otherwise due to the way EE parses from outwards inwards, the variable would be changed to the later value.
{exp:stash:get name="name"}
If you do need the variables to coexist and not overwrite each other regardless of how you nest them in the embed, you could use a dynamic context to provide a namespace and refer to it with the @ pointer from within the embed itself:
{exp:stash:set name="name" context="message_1"}John{/exp:stash:set}
{stash:embed name="message" stash:the_context="message_1"}
{exp:stash:set name="name" context="message_2"}Jane{/exp:stash:set}
{stash:embed name="message" stash:the_context="message_2"}
In the embed:
{exp:stash:context name="{stash:the_context}"}
{exp:stash:get name="@:name"}