I don't use Xbox Live, but one thought: Have you enabled NAT (network address translation)? You may want to review this article and do a little research...NAT-related problems are well-documented and the current settings may be the cause of your problems.

John