Well first off I need to ask you what xbox version are you using the brand new one? Because that has a new built in wireless adapter. My suggestion is calling your isp - (internet service provider) and asking them to reset your modem and telling them that you are having problems connecting to your internet from your xbox.
Also check to see if you have
:Wirless internet
:Wireless accessibility on your xbox