I can't add my friend to friends list, saying that they "don't exist".

I am having an issue where I can't add my friend after I playfully unfriended them. Whenever I play with them I click the add friend option above their portrait and they don't receive it. I try to add them manually through the option above the friends list and it states that they "don't exist". They try to do all the same things to me and none of it works. We also don't have each other blocked. I can invite them to party manually as well by typing out their name. Is there some way to fix this?