I have had the exact issue described here. I play on PC, friend is on a brand new Xbox. We have tried:
- Resetting/restarting game multiple times on different days
- "Removing" each other as friends (even though we can't see each other on our friends list; but when we search for each other it has a green check mark and says we are already friends, and gives us the option to "remove EA friend".)
- Uninstalling game on both ends
- On PC, I have disabled my firewalls and double checked all EA account settings
Not sure what else we can do to troubleshoot this, but four days ago we were playing together no issue, and now we can't. And it sucks ☹️