Depois de muito tempo sem jogar online no 2DS, tentei conectar o dispositivo a minha rede wireless doméstica. Era digitar a senha e me deparar com o erro 003–1101. A documentação no site da Nintendo não ajuda muito, indicando basicamente que o problema deve ser senha incorreta (não era o caso).
Depois de pesquisar um pouco, me deparo com essa thread no Reddit. Segundo o autor, a solução para o problema é simplesmente alterar nas configurações do roteador o 802.11 mode para b/g/n.
Alterei de 802.11 g/n para 802.11 b/g/n e voilá: 2DS conectado!