I can see many people here have posted that they are unable to connect to Xbox LIVE via this setup below :

Wireless Router (Sky/Other ISP) > Wireless PC > Wired to Xbox

There are a few things you have to take into consideration.

1. ICS or Bridging? I recommend Network Bridging. It is much easier and more practical as you don't need to "Share your connection" each time you turn your computer on.

2. Do you know what you are doing with ICS or Bridging?

Ok, firstly, I will explain. To bridge a connection via WIRELESS. (Wireless PC -WIRED TO- Console) You will need to FORCE COMPATIBILITY MODE.

Novice's need not worry. This step is extremely simple.

Follow this link STEP BY STEP and you won't go far wrong!

Windows XP Home Networking: Building Network Bridges

I hope this link helps you out guys/girls!

See ya on Xbox Live peeps!

Gamertag = Shadow NinjaAa