After a long time without playing online on my 2DS, I tried to connect the device to my home wireless network. Everytime I would enter the password, I got the 003–1101 error. The documentation on Nintendo's website was not that great, basically telling me that the problem was me entering the wrong password.
After searching a bit, I found this reddit thread. According to the author, the solution is simply to change the router 802.11 mode to b/g/n mode.
I changed and voilá! 2DS connected.
