Alright so the setup I have is:
Motorola SBV4200 Modem conected to a Linksys SRX200 wireless router. Which then sends the net to my PC and I have a wired routher (Linksys EZXS55W) going from the back of my pc and out to the Xbox360.
Internet connection sharing is on and its recieving the signal. When I test the connection it gets the signal, the IP address, and then it fails on the DNS test. No matter what I do I cant get it to read the signal for the DNS.
I have typed it in manually and that still didnt work. Microsoft and Linksys tech-support sites were no help.
I am not sure what authentication protocol(S) Xbox Live uses, but similar to DNAS from Sony, some ISP servers are not accepted by Microsoft/Sony.
A good example would be the ISP servers used by hotel chains to offer their dismal highspeed internet in their rooms.
If you do as the other two suggested and plug it directly into your connection, but make no progress, then the authentication is the issue.
Microsoft will tell you to talk to your ISP.
Do you have any documentation to back that up? It seems weird that Microsoft would refuse connections from certain ISPs. Or do you mean that certain ISPs just don't support whatever Microsoft requires? I was under the impression that all you needed was a DHCP server to assign the Xbox an IP address? I have a software firewall and it works fine with Live and PS2.