Usually when this message "Failed to connect to map server" shows for more than one user(so not only yourself) like a group of friends or anyone trying to go into a private map, it actually tends to be that the map process itself on the server has gotten stuck and will not let anyone in to the map. Since this is server bound it will not really matter if a user restart their game or go on another character, the same message will still persist if as mentioned earlier, it's something that happens to more than one user trying connect to a certain map. There's no direct fix so a user could get into these kind of maps that are stuck.
In some cases when the message "Failed to connect to map server" is more directed at a certain user and other users can go into the map and play it just fine, it tends to sort itself out after giving it a while, but only then. But when all users face the same message to a certain map it just will not work and there's nothing users can do to sort it I'm afraid.
If I will take my own maps as an example. The FeralCity map and my map pack, these custom maps tend to have quite a few users running around in them but far from constant activity lasting 24/7 within these maps. Since people come and go a lot, and the maps do not constantly have one active user inside, it will start and stop, start and stop, start and stop everytime someone goes into the map or leaves it making it empty. Every time this happens the process itself on the server will kill itself and start up again, which also leads to higher risks of it actually getting stuck(Why it happens I still do not know and this is what I can make of it at this point). When a said map do get stuck you will face the "failed to connect to map server".
The only thing that directly will fix this is if we have a server restart, shutting it down temporarily and forcing all users playing to go offline, usually we try to have one here and there during early morning hours when no one is really online, but it can take some time to actually get to doing such so all you can do is to hang in there. The only way to play on a certain map you made right away, would be if you exported a new version of the stuck map(if you made it) and go into the right portal in cape.
So if the case is that ALL users have issues with a certain map, there's nothing but a server restart that can fix it and we try not to have those too often since users get a bit derpy when the game is/goes offline.'
Hope that explains it.