I had assumed that it would restart on the same seed, as in "go back to the very first state of the current game", because the word "restart" on its own doesn't make either choice the "only" choice in English. edit: in fact, the one time i was tempted to use it, I'd have been very disappointed to get a new map seed.
I'd suggest something slightly longer, but roughly "start a new map", or "restart and randomize map", or "restart on a new map", or something.

