Changing their NAT settings from Strict/Moderate to Open.
What you need:
1.Patience!
2.Pen and paper
3.Your router model
You will know you have either strict or moderate settings when you see the image below after running Xbox LIVE connection test:

Hope this tutorial will help change this so you get the most out of your connection on Xbox LIVE and the ability to join your friends in session! (Windows guide and one xbox only, may also apply to Playstation Network)
Note:There are many routers out there and some options may not be available to everyone. Consult your routers manual/guide if having difficulty later on
Always try have your connection wired instead of wireless-it will be alot faster and reliable.
Step1:
Open the cmd prompt. Select the Start button from the windows menu and search "cmd".Select the first option. A black box will appear. Type "ipconfig/all" without the quotes. A list of information will appear. Note the number for "default gateway". It should be in the form 192.168.x.xx. This is known as an I.P address. Note also "subnet mask"( nearly always 255.255.255.0)
Step 2:
Open an internet browser( Google chrome/Firefox/ Internet explorer) and type this number into the url bar to bring up your routers configuration page. If prompted for a password it is usually Username:
admin/administrator Password:
password. If these do not work check the guide/manual that came with the router.
Step 3:
On your routers configuration page find DHCP server ( usually in the configuration settings of the advance tab-can take a while to find but have a good search around). It will have a start I.P address and an End I.P address. Note these two addresses.
Step 4:
For this step, go on to your xbox. While on "My xbox" blade navigate over to the system settings tab. Select by pressing A button and move down to "Network settings". Select "Configure Network" and press A. There should be two options-Automatic and Manual. Select Manual. Press A to edit your settings.
For I.P address, enter an address within your DHCP server range found within step 3- It should be something like 192.168.x.yy and note the address you have entered for later on(
Very Important).
For subnet mask, enter the address found in step1, usually 255.255.255.0
For default, gateway enter the address that you typed into your browser and found in step1 and exit out.
There will also be the option to edit your DNS settings on the same tab. Select manual and enter the the default gateway address you found as your primary DNS server. Enter 8.8.4.4 as secondary address-This is Googles DNS server ( Not as important as primary however) and your done on the xbox for the moment.
Step 5:
Log onto you routers configuration page again
Enable UPnP.(May involve a bit of searching within the configuration page).
Universal Plug and Play (UPnP) is a set of networking protocols promulgated by the UPnP Forum. The goals of UPnP are to allow devices to connect seamlessly and to simplify the implementation of networks in the home (data sharing, communications, and entertainment) and in corporate environments for simplified installation of computer components.
Try to enable UPnp. It will help your connection alot for gaming/streaming etc
Step 6:
There are 2 options in this step to get your NAT to open(Don't use both):
1.Using DMZ (may not be available on some routers and may be risky(read below))
2.Port Forwarding(Safer but more time consuming and trickier)
1. A Demilitarised Zone (DMZ) is a zone (IP address) that is external to the Firewall. In layman's terms it exposes one computer or console to the internet with no protection. This isn't recommended for computers, but for a games console it is perfect(In my opinion)!
2.The vast majority of home networks have a Firewall unless disabled. Computers and Games consoles are protected from malicious content on the internet by the Firewall. The Firewall can also stop information that needs to be sent and received. In this scenario, the information that the Xbox trying to send or receive is being limited. If the specific ports are opened, then the Xbox can send and receive all the information that it needs to.
For 1., Find your DMZ option and enter the I.P address that you entered for your xbox( also known as DMZ Host) in part 4 and your done! All ports will be opened and NAT will be set to open( at own risk)
For 2.,There is a great site that will help you forward your ports for xbox live for all sorts of routers:
http://portforward.com/english/routers/port_forwarding/routerindex.htm find you router and default guide for the router and follow the steps to open the following ports.
Ports needed open for Xbox Live are:
TCP 80
UDP 88
TCP 88
UDP 3074
TCP 3074
UDP 53
TCP 53
Name it Xbox Live and put the ports in seperately. For example;
Service Name : Xbox Live 1
Service Type: TCP
Starting Port: 80
Ending Port: 80
Server IP Address : YOUR XBOX'S IP that you gave it earlier.
save settings, reboot if needed and exit out
Step 7:
Test xbox live connection.You should get this

Hope this works for all! Spent a lot of time creating this and making it as simple as I could so please acknowledge. Any questions feel free to ask!!