When trying to invite another player, it says I have no friends.

I was trying to invite a friend to a cross-platform game. For reference, they are on Switch. It had worked previously in the day (may have been a LAN connection at the time, but not 100% sure). When I tried to invite them later in the day, it displays that I have no friends. When they try to invite me to their game, it also display the same message. We are both signed in with our separate Microsoft accounts.
Edit: Also does the same thing when trying to invite a player from my phone.