We have a comcast gateway, if that makes a difference.
If you mean one of those SMC gateways[SMCD3GNV] then your in for a treat.
Pop open the secret screen of your roku box using these commands:there must be no error message on the screen before you do this.
Fast Forward x3
There should be a part where the Roku displays the IP it's getting from your router.
If it's not 0.0.0.0 then select "update software" from the lower right portion of that page.
After the Roku goes through the update, you should be able to finish the setup just following the instructions on your TV.
If it didn't work the first time, reboot your gateway and the roku. Connect the Roku to your gateway again - don't worry if you get a red light, this is just so that the roku can get a new IP before trying the update. Do the update from the secret screen. See if it works the second time around.