After months of playing with one friend in each other's worlds, both my friend and I are getting the error Unable to Connect to World when attempting to play together.

Both of us are playing on the Xbox One system.

Per MCPE-36190, I have confirmed NAT Type to be open.

I'm concerned that so many people are having this issue in the MCPE-36190 ticket that we will not be able to play together again. 

Please advise for resolution.