We had this same problem when my brother got back from abroad with a new laptop on our network. We couldn't get either of them online at the same time. You are probably going to have to put in the IP address of your router manually into your Xbox.
When you do a connection test does it say IP failed?









