[Angrist]

There were two ways of adding people: invite them through Miiverse, where they got a message saying they got invited; or add their ID in the friend menu, where you just had to wait until the other person did the same thing. He wouldn't get a notification.

It seems like they have fixed that, but that explains why some friend invites never got through.