When I had that error came up I resolved it be resetting my router AND my 3DS and moving closer to the router. ~ I knew it wasn't an issue with firewalls or the person as we had connected before.
Maybe make sure both you and the person you are connecting to does this. - Weirdly when I had this issue both me and the person I was connecting to had just came back from other friends towns.
I have that problem too. But no solutions have worked for me. I update my system, I updated the data and everything! Another thing is I can't do it, but my sister can and she is always right next to me when we go to someone's town by internet