In the Nintendo 3DS Friends app, I'm trying to register a new friend.
In the Friends app, I click the orange "Add friend" icon, then in the dialog that appears with the choices "Local" and "Internet", I tap "Internet".
At this point, I get the error: "You cannot use Internet registration because you are not online."
The status bar on the top screen of the 3DS does show "Internet", indicating that I am online. I can successfully use the 3DS to do other online things such as browse the e-shop.
How can I get this working?