First, have you had an opportunity to try some of the connectivity troubleshooting options provided by Microsoft for Xbox LIVE? For example, either Xbox LIVE Connection Problems or Xbox LIVE Connection Solution (aka Connection Wizard)? If so, what was the exact error(s) that either were reporting?
Typically, when your console is able to access the Internet, but not to Xbox LIVE, the issue can be one of at least three things: 1) ICMP, 2) NAT, or 3) MTU errors. Were any of these reported when you ran the connectivity tests?