list of compatible routers here
http://www.xbox.com/en-US/live/conne...terlanding.htm
i have a dlink DGL-4300 connected fine to live and downloading from marketplace, haven't played online though.
you could try forwarding these ports to the xbox
* External Ports 88 UDP
* External Ports 3074 TCP & UDP