You mention your router, yet you say you use Internet Connection Sharing (ICS)?
If you have a router, then you should really connect the Xbox directly to that, rather than using ICS.
As morrk said, you need to forward the XBL ports, to be able have "Open NAT" [Unless your router has UPnP, in which case you shouldn't need to forward ports].