Hey !
Same problem here, i just spent 3 hours trying to understand something, before googling and landing here 
I’m using the steam onlineSub.
Servertravel works very well before in start a session. As soon as i start my steam session i get the “Not Traveling” message.
When i add this before calling ServerTravel:
AGameModeBase* ThisGMBase = GetWorld()->GetAuthGameMode();
if (!ThisGMBase->CanServerTravel(TargetMap, false))
{
GEngine->AddOnScreenDebugMessage(-1, 10.f, FColor::Red, TEXT("CAN'T TRAVEL"));
}
I get my “can’t travel” message, so CanServerTravel is failing somehow, but i couldn’t (yet ?) locate where the function fails, i get none of the LogGameMode messages from CanServerTravel, and i can’t find the “Not traveling” message in the GameModeBase class.
The steam onlineSub has been updated from v132 to v139 with 4.16, i though it might be related to that, are you guys using steam as well, or is the problem more general ?
I like the way UE4 evolves at the speed of light, but since a few versions, i find myself a bit scared by each new version because everytime i know it will take me a week or two of regressions corrections and bugs reports before i can get back to where i was 
Did anyone open a bug report ?
Cheers
Cedric