I'm close to hitting lvl 31 so I've had some experience with this issue.
Restarting Pokemon Go has been a huge success for most but I've seen cases myself where it did not work even then.
Ever since I've always given the servers some time after the restart, e.g. just a few minutes, to let the name sink in. Every evolution has worked since then. I've evolved a few and so have my friends.
It's possible that the game is picking up the new name from the phone's cache (which I happen to clear out just in case before evolving) instead of picking it right up from the server. Clearing the cache for this specific app should enforce the game to load the name from the server if it used to pick it up from cache.
The time that occurs during the restart might be enough but like I said: I've seen cases where it was simply not enough. It's very possible that restarting is not required at all, simply waiting might be enough. Better safe than sorry though!
Conclusion: Restart and give it some time. Consider clearing the game's cache if you want to be extra safe and make sure the game can't load the name from your phone and force it to load it from the server.
I understand that this is a little messy and it's hard to give a 100% working one way answer but without spoofing and experimenting a lot with different ways it's safer to do all the things that make it likely to work.
EDIT: A few updates after I posted this it no longer seems to work. I'm not sure whether it was luck all along or whether it was a bug that allowed us to do this multiple times, if so it seems to have been fixed. It seems to be pretty much random now but if anything changes I'll update.