Change the security settings. The 3ds needs to use AES. My router is set to TKIP/AES and works fine. I remember having to change to this setting because when I originally got my 3ds, it wouldn't connect.
Did you try changing the wireless encryption type as suggested? The DS should be set to use WPA2-PSK (AES), while the router should be set to WPA2-PSK (AES), WPA2-PSK (TKIP/AES), or WPA2-PSK (TKIP). Try all three, in that order.
Well you certainly don't want that. I also would advise strongly against using WPA, you should most definitely use a form of WPA2. Preferably WPA2-AES.