I believe releasing the IP from your computer will just fetch it a new IP from the router, not get your router a new WAN IP from the modem. That's what the Linksys help is probably referring to. Open a browser and go to 192.168.1.1 Leave the username blank and type admin for the password. Once you're in there, see if the router is getting a WAN IP. I'd tell you specifically how to do this but I don't have access to one at the moment... it should be in some sort of status tab though. You can also release/renew the WAN IP from the router's web interface.
Alternately, you could start fresh. Power cycle the modem (this may get you a new IP anyway) without connecting it to your computer, and when it's finished starting up and the leds for internet and everything are on, connect and turn on your router. At this point, if you don't have internet access, hit the setup button on the front of the router (you may need to hold it a couple of seconds, the light should go off and it should begin flashing) and let the router reboot and do it's thing. This is usually all I need to do to get one working. These instructions should apply to all the WRT54G series routers. I don't know if the Ns are different.
Lastly, be sure to go in the web interface and enable security (use WPA or WPA2!), and change the password to access the router's web interface.
One other issue I've run into once is a router and modem having the same default IP address. I'm just throwing this out there, but I doubt it's a problem.