More ideas:
My brother connects via the xbox one wireless connection where as I am wired. Are other people using the wireless functionality?
It may be due to internet providers? I and my brother both have comcast.
If anyone can connect to a random game, perhaps take the time to ask them about their setup. We know connections are possible, we don't know what makes some (random) connections successful.
