I’ve tried everything and this problem still is a thing. Havent seen any other person with this problem 
Error images -
i am on PC and live in india (I was able to connect and play online perfectly before this randomly showed up)
Try updating your game and see if that helps… cheers
Hi, i had the same issue. Changing my Teredo settings via the command line via this command worked for me: netsh interface teredo set state type=enterpriseclient
If that doesn’t help, check out this post:
The first reply links to this post: https://www.reddit.com/r/killerinstinct/comments/4cvo7c/to_those_of_you_unable_to_resolve_your_teredo/
I also found this: Xbox Support
Hope this helps, good luck!