Users cannot be added to contact groups

A couple of users already told me they cannot add individual users to their individual contact groups within Teams. The users, which cannot be added don't match. For example I can add user A but user B cannot add user A.

I get this error message:

Any ideas? We are currently in the process of establishing an Exchange Hybrid setup. Exchange Online and on Premise are not synced properly yet, but I guess that should not matter?

Thanks in advance.

Best regards