I'm guessing that you're using 802.11b/g?
If so, changing the channel on the wireless is a good idea, I'd try moving 3 or 4 channels from where you started. Most likely, you've got another wireless device trying to use the same channel. (i.e. a wireless phone, or a neighbor's computer network). Also, you can check for common sources of interference, like microwaves, florescent lights, metal walls in the way... You're dealing with a radio, so if there's anything that would interfere with signal on a cell phone, or a remote control car, it might interfere with your wifi as well.
If that doesn't work, or you can't figure out how to change the channel, you can call the company that made the router, and talk to tech support. That might just be an ordinary configuration error, and even if it's not, they might be able to help (Be polite, and patient, if they seem to be running through a lot of basic stuff, that's where most people make a small slipup).