just off the top of my head (and admittedly without real firsthand with XBOX), have you tried running a speed and/or latency test to see what your connection is like? ive run/admin'd a few game servers both locally and colocated, and many of the symptoms you describe sound like either not enough upload bandwidth available or bad latency to the internet/backbone. would also explain why things appear fine on your end (youre connecting via your own LAN. comparatively massive bandwidth available with <10ms latency) and not to those on the WAN side.
Bookmarks