the router must be:
802.11B
WEB 64/128 bit with a valid key
Channels 1, 6 or 11
SSID set to public broadcast
Nintendo recommends that you change the SSID from the defult one that shipped with the router. this is because the nds will attempt to find the wifi connection via the SSID, and two or more matching SSIDs can cause errors. Also if you are using MAC address security (as suggested by thebobevil) then you must get the MAC address of your nds and add it to your router. Nintendo also recommends that you turn off any range enhancing features as they require a G or N network and can cause wifi problems with the nds.
if all that is set up correctly double check that the WEP key and SSID are correct in your nds. try to connect from different spots in the room. sometimes the router just doesn't kick the signal out the way you think it would.
on the back of your nds is a 1800 number where you can call nintendo for free support. give it a go.
finally, if you are setting up wifi for the first time.. make sure its actually on! =)
-another world