When I try to add my friend, it says his name does not exist.

When I try to add my friend, it says his name does not exist. My other friends can add him just fine yet, for me, I can't seem to find him and he can't seem to find me. When we try to add each other, it says "The name ___ does not exist." However, we can invite each other to game lobbies.