Everything was connecting except I was getting the error XBOX Live not found.
I thought I was banned but I wasn't.
I tried connecting my xbox directly to the cable modem and it worked!
I narrowed it down to my router. I have a Linksys WRT54GS.
The way I got it to work was by setting a StaticIP on my xbox.
Your Static IP should be something that your router wouldnt assign to anything else.
In which case you SHOULD NOT use something like 192.168.1.101.
You SHOULD use something like what I did which is 192.168.1.5.
Then I went into the Linksys UI and went into the thing called DMZ.
I ENABLED the DMZ Host IP Address, and then I entered in my XBOX's static IP which is 192.168.1.5.
And that's it. It had nothing to do with my NAT Firewall or anything. No need to open up certain ports. DMZ basecally opens it up directly to the internet.