Additional Network Ports for Multiplayer Gaming: Xbox one S latency problems..

Could you provide the make and model of your wireless router, and your modem as well.

Wireless is not preferable as a connection type for time sensitive games. You should consider to find a wired solution instead

Did you try changing your NAT type? The helpdoc says:

Open:

With an OPEN NAT type, you’re able to chat with other people, as well as

join and host multiplayer games with people who have any NAT type on

their network

Moderate:
With a MODERATE NAT type, you’re able to chat and play multiplayer games

with some people; however, you might not be able to hear or play with

others, and normally you won’t be chosen as the host of a match.

Strict:

With a STRICT NAT type, you’re only able to chat and play multiplayer

games with people who have an OPEN NAT type. You can’t be chosen as the

host of a match.

-- So I take that to mean if you have STRICT NAT, and if anyone in the group DOES NOT have an OPEN NAT type you are going to have problems.

Are you both running STRICT NAT type?

Ports required to use Xbox Live

These ports must be open for Xbox Live to work:

• Port 88 (UDP)
• Port 3074 (UDP and TCP)
• Port 53 (UDP and TCP)
• Port 80 (TCP)
• Port 500 (UDP)
• Port 3544 (UDP)
• Port 4500 (UDP)

Note Some game developers require you to open additional ports. You should always check the game developer's website to see if the game you're playing needs additional ports to work. We've gathered some ports you might need
and have added them to the
Additional Network Ports for Multiplayer Gaming forum.

If you're connected to a network through your workplace or school, ask the network administrator to open these ports.

If you receive a NAT warning when you connect to Xbox Live, see the
Xbox One Multiplayer Game Solution

What games/apps are running slowly? When you are done with an app or game do you Exit out of it using the start button or just go to the Home screen?

I have the same problem after this latest update and Microsoft doesn't help to open your ports anymore!!!! you have to contact your internet provider. I was connected by ethernet/wired and got this same message about the teredo... (my internet provider
could not seem to help with this either. so i connected wireless and Bam it worked for me. and stated that my NAT was open.... hope this helps you

yes m8 it did thanks you but sometimes its still saying the same at least is not always. thanks

Try changing the DNS on Xbox One.

Use Google.

The Google Public DNS IP addresses (IPv4) are as follows:

Primary DNS: 8.8.8.8

Secondary DNS: 8.8.4.4

After changing, restart Xbox One.

It worked for me.