Sign up for Office 365
Learn more about Office 365
Are you meaning the issue only affect you and one of your contacts? If so, I would like to confirm when you added this contact, which privacy relationship you had chosen for this contact? It sounds that one of you and your contact have chosen 'Blocked Contact' for the other. Please try to change the privacy relationship for the contact to see if there is any improvements.
For more information, please refer to Control access to your presence information.
Are the Lync federation sides both Lync Online environment, or one Lync Online, one Lync on-premises 2010 server? Actually to configure Lync federation in Office 365, you need to enable the federation for both sides. Please ensure that the other side has also enabled federation for your domain.
In addition, here is an video for troubleshooting Lync federation issues for your reference:
VIDEO: Troubleshooting Domain Federation for Lync
Federation is activated in the Lync Online environment, and in the on-premises server (this server has open federation). The account in the on-premises server also has multiple other Lync Online accounts attached, and thay are working perfectly.
Has the issue been resolved now? Please let us know if you need more assistance.