I'm not all that familiar with the ol' Xbox, but whenever I plugged in directly it would pick it up without the need for a reboot. I'm sure you already have, but after plugging in, do you go to the middle button menu (because I'm so excellent with terminology) and hit the Connect to Xbox Live option? It must be something with your router, does it do the same for your computers? It may be worth looking into configuring your modem. Usually you just have to type the IP in your browser and enter the necessary username/password.
Certainly no expert here! We have some serious networking dudes on these forums, though, so maybe one of them can give you less newbish info. Good luck, bro!