On the microsoft website they have instructions here: click here
You can either have a:
1.) Direct Connection
2.) Router Connection
3.) Internet Connection Sharing
I've had problems before when setting up XBox Live that was due to the incompatibility of a router but i'm asssuming your case is different. Try following the instructions I provided you in the above link and see how you get on.
If you still have problems report back i'm sure someone will able to help.
( They should be a customer service number for XBox Support who I believe may able to help also. This is what they got on the website:
Assistance by phone seven days a week.
0800 587 1102