We had the same issues - but were able to search for our wireless network and then use our WEP to log on. It would show we were connected, but then wouldn't find the IP address of the xbox. Once I disabled the WEP (which I really didn't want to do) we were able to log onto the xbox. I'm still working on this. But you can also try the connection wizard on the linksys page which will allow you to save the settings onto a usb stick that you plug into the back of the xbox to download the router information.
On the main menu of the XBOX, use your joystick to click on settings, network settings, then click on advanced, then click on wireless, then click on settings, then click on security key. There it will allow you to input your wep key.